Guest User

Untitled

a guest
Feb 7th, 2017
1,370
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string.h>
  3. #include <vector>
  4. #include <map>
  5. using namespace std;
  6. map<string,int> m;
  7. pair<int,int> arr[100005];
  8. vector<pair<int,int> > v[100005];
  9. vector<pair<pair<int,int>,pair<int,int> > > sus;
  10. bool valid[100005],vis[100005];
  11. int n,cum[100005];
  12. int find(int x)
  13. {
  14.     if (x!=arr[x].first)
  15.     x=find(arr[x].first);
  16.     return arr[x].first;
  17. }
  18. bool Union(int x,int y)
  19. {
  20.     x=find(x);
  21.     y=find(y);
  22.     if (x==y)
  23.     return 0;
  24.     if (arr[x].second<arr[y].second)
  25.     arr[x].first=y;
  26.     else if (arr[x].second>arr[y].second)
  27.     arr[y].first=x;
  28.     else
  29.     {
  30.         arr[x].first=y;
  31.         arr[y].second++;
  32.     }
  33.     return 1;
  34. }
  35. void dfs(int node,int pnode,int x)
  36. {
  37.     vis[node]=1;
  38.     cum[node]=x;
  39.     for (int i=0;i<v[node].size();i++)
  40.     {
  41.         if (v[node][i].first!=pnode)
  42.         dfs(v[node][i].first,node,(x^v[node][i].second));
  43.     }
  44. }
  45. void preprocess()
  46. {
  47.     for (int i=0;i<n;i++)
  48.     {
  49.         if (!vis[i])
  50.         dfs(i,i,0);
  51.     }
  52.     for (int i=0;i<sus.size();i++)
  53.     {
  54.         int x=sus[i].first.first,y=sus[i].first.second,idx=sus[i].second.first,r=sus[i].second.second;
  55.         if ((cum[x]^cum[y])==r)
  56.         valid[idx]=1;
  57.         else
  58.         valid[idx]=0;
  59.     }
  60. }
  61. int main()
  62. {
  63.     int q1,q2;
  64.     cin >> n >> q1 >> q2;
  65.     for (int i=0;i<n;i++)
  66.     {
  67.         string s;
  68.         cin >> s;
  69.         m[s]=i;
  70.         arr[i]=make_pair(i,0);
  71.     }
  72.     for (int i=0;i<q1;i++)
  73.     {
  74.         int t;
  75.         string s1,s2;
  76.         cin >> t >> s1 >> s2;
  77.         int x=m[s1],y=m[s2];
  78.         if (Union(x,y))
  79.         {
  80.             v[x].push_back(make_pair(y,t-1));
  81.             v[y].push_back(make_pair(x,t-1));
  82.             valid[i]=1;
  83.         }
  84.         else
  85.         sus.push_back(make_pair(make_pair(x,y),make_pair(i,t-1)));
  86.     }
  87.     preprocess();
  88.     for (int i=0;i<q1;i++)
  89.     {
  90.         if (valid[i])
  91.         cout << "YES" << endl;
  92.         else
  93.         cout << "NO" << endl;
  94.     }
  95.     while (q2--)
  96.     {
  97.         int t;
  98.         string s1,s2;
  99.         cin >> s1 >> s2;
  100.         int x=m[s1],y=m[s2];
  101.         if (find(x)!=find(y))
  102.         cout << 3 << endl;
  103.         else if (cum[x]^cum[y])
  104.         cout << 2 << endl;
  105.         else
  106.         cout << 1 << endl;
  107.     }
  108. }
RAW Paste Data