tuki2501

Bạn của bạn

Aug 2nd, 2021
585
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 200005;
  5. const int blockSize = sqrt(N);
  6.  
  7. vector<int> vadj[N];
  8. unordered_set<int> sadj[N], ladj[N];
  9. bool isLarge[N];
  10.  
  11. void addEdge(int u, int v) {
  12.   if (!sadj[u].count(v)) {
  13.     vadj[u].push_back(v);
  14.     vadj[v].push_back(u);
  15.     sadj[u].insert(v);
  16.     sadj[v].insert(u);
  17.   }
  18. }
  19.  
  20. int main() {
  21.   int n, m;
  22.   scanf("%d%d", &n, &m);
  23.   for (int i = 1; i <= m; i++) {
  24.     int u, v;
  25.     scanf("%d%d", &u, &v);
  26.     addEdge(u, v);
  27.   }
  28.   for (int i = 1; i <= n; i++) {
  29.     if ((int) vadj[i].size() > blockSize) {
  30.       isLarge[i] = 1;
  31.     }
  32.   }
  33.   for (int i = 1; i <= n; i++) {
  34.     vector<int> v;
  35.     for (auto &j : vadj[i]) {
  36.       if (isLarge[j]) v.push_back(j);
  37.     }
  38.     for (int j = 0; j + 1 < (int) v.size(); j++)
  39.     for (int k = j + 1; k < (int) v.size(); k++) {
  40.       ladj[v[j]].insert(v[k]);
  41.       ladj[v[k]].insert(v[j]);
  42.     }
  43.   }
  44.   int q; scanf("%d", &q);
  45.   while (q--) {
  46.     int t, x, y;
  47.     scanf("%d%d%d", &t, &x, &y);
  48.     if (t == 1) {
  49.       addEdge(x, y);
  50.     }
  51.     else {
  52.       if (sadj[x].count(y)) {
  53.         printf("YES\n");
  54.         continue;
  55.       }
  56.       if (!isLarge[x] && !isLarge[y]) {
  57.         if (vadj[x].size() > vadj[y].size()) {
  58.           swap(x, y);
  59.         }
  60.         bool flag = 0;
  61.         for (auto &i : vadj[x]) {
  62.           if (sadj[i].count(y)) {
  63.             flag = 1;
  64.             break;
  65.           }
  66.         }
  67.         printf(flag ? "YES" : "NO");
  68.         putchar('\n');
  69.       }
  70.       else if ((!isLarge[x] && isLarge[y]) || (isLarge[x] && !isLarge[y])) {
  71.         if (isLarge[x]) swap(x, y);
  72.         bool flag = 0;
  73.         for (auto &i : vadj[x]) {
  74.           if (sadj[i].count(y)) {
  75.             flag = 1;
  76.             break;
  77.           }
  78.         }
  79.         printf(flag ? "YES" : "NO");
  80.         putchar('\n');
  81.       }
  82.       else {
  83.         printf(ladj[x].count(y) ? "YES" : "NO");
  84.         putchar('\n');
  85.       }
  86.     }
  87.   }
  88. }
  89.  
RAW Paste Data