YEZAELP

CUBE-224: Lion Army

Jun 22nd, 2021
629
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N = 3e5;
  5. const int mod = 1e9 + 7;
  6. int di[N+10];
  7. int parent[2*N+10];
  8. int cnt;
  9.  
  10. int root(int u){
  11.     if(parent[u] == u) return u;
  12.     return parent[u] = root(parent[u]);
  13. }
  14.  
  15. void mrg(int u, int v){
  16.     u = root(parent[u]);
  17.     v = root(parent[v]);
  18.     if(u == v) return;
  19.     parent[v] = u;
  20.     cnt --;
  21. }
  22.  
  23. int main(){
  24.  
  25.     int n, m;
  26.     scanf("%d%d", &n, &m);
  27.     cnt = 2*n;
  28.  
  29.     di[0] = 1;
  30.     for(int i=1;i<=n;i++){
  31.         di[i] = di[i-1] * 2;
  32.         di[i] %= mod;
  33.     }
  34.  
  35.     for(int i=1;i<=2*n;i++)
  36.         parent[i] = i;
  37.  
  38.     bool check = true;
  39.     for(int i=1;i<=m;i++){
  40.         int opr, a, b;
  41.         scanf("%d%d%d", &opr, &a, &b);
  42.         if(!check){
  43.             printf("0\n");
  44.             continue;
  45.         }
  46.         /// a = Aa, b = Ab
  47.         /// a + n = Ha, b + n = Hb
  48.         if(opr == 1){
  49.             mrg(a, b);
  50.             mrg(a+n, b+n);
  51.         }
  52.         else {
  53.             mrg(a, b+n);
  54.             mrg(a+n, b);
  55.         }
  56.         if(root(a) == root(a + n) or root(b) == root(b + n)) { /// Ha != Aa and Hb != Ab
  57.             check = false;
  58.             printf("0\n");
  59.             continue;
  60.         }
  61.         printf("%d\n", di[cnt/2]);
  62.     }
  63.  
  64.     return 0;
  65. }
  66.  
RAW Paste Data