Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define pb push_back
- #define mp make_pair
- #define clr(i, j) memset(i, j, sizeof i)
- typedef long long ll;
- typedef unsigned long long ull ;
- typedef pair<int,int> pii;
- const int N = 1e5+1;
- int n, m, q, x, y, t, xroot, yroot;
- vector<int> adj[N];
- string a, b;
- map<string, int> p;
- pii sub[N];
- int find(int x)
- {
- if(x == sub[x].first)
- return x;
- return sub[x].first = find(sub[x].first);
- }
- void Union(int x, int y)
- {
- if(x == y)
- return;
- xroot = find(x);
- yroot = find(y);
- if(sub[yroot].second > sub[xroot].second)
- swap(xroot, yroot);
- sub[yroot].first = sub[xroot].first;
- if(sub[xroot].second == sub[yroot].second)
- sub[xroot].second++;
- //cout << xroot << " " << yroot << endl;
- for(int i=0; i<adj[yroot].size(); i++)
- adj[xroot].pb(adj[yroot][i]);
- sort(adj[xroot].begin(), adj[xroot].end());
- }
- int main()
- {
- cin >> n >> m >> q;
- for(int i=0; i<n; i++)
- {
- sub[i].first = i;
- sub[i].second = 0;
- cin >> a;
- p[a] = i;
- }
- for(int i=0; i<m; i++)
- {
- cin >> t >> a >> b;
- //cout << *s.find(a) << " " << endl;
- x = find(p[a]), y = find(p[b]);
- if(( binary_search(adj[x].begin(), adj[x].end(), y) && t == 1) || (t == 2 && x == y))
- cout << "NO" << endl;
- else
- {
- cout << "YES" << endl;
- if(t == 1)
- Union(x, y);
- else
- {
- adj[x].pb(y), adj[y].pb(x);
- if(adj[x].size() > 1)
- Union(adj[x][adj[x].size()-1], adj[x][adj[x].size()-2]);
- if(adj[y].size() > 1)
- Union(adj[y][adj[y].size()-1], adj[y][adj[y].size()-2]);
- }
- }
- }
- for(int i=0; i<q; i++)
- {
- cin >> a >> b;
- x = find(p[a]), y = find(p[b]);
- if(x == y)
- cout << 1 << endl;
- else if(binary_search(adj[x].begin(), adj[x].end(), y))
- cout << 2 << endl;
- else
- cout << 3 << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement