YEZAELP

CUBE-226: Traveling Pooh

Jun 19th, 2021
970
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 = 2e5;
  5. int n, q;
  6. int ar[N+10];
  7. int color[N+10], order[N+10];
  8.  
  9. void dfs(int u, int ord, int c){
  10.     if(color[u] != 0) return;
  11.     order[u] = ord;
  12.     color[u] = c;
  13.     int v = ar[u];
  14.     dfs(v, ord+1, c);
  15. }
  16.  
  17. bool check(){
  18.     int s, e, a, b;
  19.     scanf("%d%d%d%d", &s, &e, &a, &b);
  20.     if(color[s] == color[e]){
  21.         if((color[e] == color[a] and color[a] != color[b])
  22.         or (color[e] == color[b] and color[a] != color[b])
  23.         or (color[a] == color[b] and color[a] != color[s])
  24.         or (color[a] != color[b] and color[a] != color[s] and color[b] != color[s]))
  25.             return false;
  26.         int os = order[s], oe = order[e];
  27.         int oa = order[a], ob = order[b];
  28.         if(oa > ob) swap(oa, ob);
  29.         return (oa < os and os <= ob) != (oa < oe and oe <= ob);
  30.     }
  31.     else{
  32.         if(color[s] == color[a] and color[e] == color[b]) return false;
  33.         else if(color[s] == color[b] and color[e] == color[a]) return false;
  34.         return true;
  35.     }
  36. }
  37.  
  38. int main(){
  39.  
  40.     scanf("%d%d", &n, &q);
  41.  
  42.     for(int i=1;i<=n;i++) scanf("%d", &ar[i]);
  43.  
  44.     int c = 1;
  45.     for(int i=1;i<=n;i++){
  46.         if(color[i] == 0){
  47.             dfs(i, 1, c);
  48.             c ++;
  49.         }
  50.     }
  51.  
  52.     while(q --){
  53.         if(check()) printf("SURVIVE\n");
  54.         else printf("DEAD\n");
  55.     }
  56.  
  57.     return 0;
  58. }
  59.  
RAW Paste Data