daily pastebin goal
3%
SHARE
TWEET

Untitled

a guest May 16th, 2018 108 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <iostream>
  3. #include <vector>
  4. #include <string>
  5. #include <queue>
  6. using namespace std;
  7. vector <bool> konch1, konch2, used1, used2;
  8. vector <vector <int>> pereh1, pereh2;
  9. queue <pair <int, int>> Q;
  10.  
  11. bool check(){
  12.     Q.push(pair <int, int> (1, 1));
  13.     pair <int, int> a;
  14.     int x, y;
  15.     while (!Q.empty()){
  16.         a = Q.front();
  17.         Q.pop();
  18.         if(!a.first && !a.second){
  19.             break;
  20.         }
  21.         if(konch1[a.first] != konch2[a.second]) return false;
  22.         for(int i = 0; i < 26; i++){
  23.             x = pereh1[i][a.first];
  24.             y = pereh2[i][a.second];
  25.             if((!used1[x] || !used2[y]) && (x != -1 || y != -1)){
  26.                 Q.push(pair <int, int> (x, y));
  27.             }
  28.             if(x != -1) used1[x] = true;
  29.             if(y != -1) used2[y] = true;
  30.         }
  31.     }
  32.     return true;
  33. }
  34.  
  35. int main(){
  36.     ifstream fin ("equivalence.in");
  37.     ofstream fout ("equivalence.out");
  38.     int n, m, k, a, b;
  39.     fin >> n >> m >> k;
  40.     konch1.resize(n+1);
  41.     used1.resize(n+1);
  42.     pereh1.resize(26);
  43.     pereh2.resize(26);
  44.     for(int i = 0; i < 26; i++){
  45.         pereh1[i].resize(n+1);
  46.         for(int j = 0; j <= n; j++){
  47.             pereh1[i][j] = -1;
  48.         }
  49.     }
  50.     for(int i = 0; i < k; i++){
  51.         fin >> a;
  52.         konch1[a] = true;
  53.     }
  54.     char c;
  55.     for(int i = 0; i < m; i++){
  56.         fin >> a >> b >> c;
  57.         pereh1[c - 'a'][a] = b;
  58.     }
  59.     fin >> n >> m >> k;
  60.     konch2.resize(n+1);
  61.     used2.resize(n+1);
  62.     for(int i = 0; i < 26; i++){
  63.         pereh2[i].resize(n+1);
  64.         for(int j = 0; j <= n; j++){
  65.             pereh2[i][j] = -1;
  66.         }
  67.     }
  68.     for(int i = 0; i < k; i++){
  69.         fin >> a;
  70.         konch2[a] = true;
  71.     }
  72.     for(int i = 0; i < m; i++){
  73.         fin >> a >> b >> c;
  74.         pereh2[c - 'a'][a] = b;
  75.     }
  76.     used1[0] = true;
  77.     used2[0] = true;
  78.     check() ? fout << "YES" : fout << "NO";
  79.     return 0;
  80. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top