mickypinata

CUBE-T226: Traveling Pooh

Jun 18th, 2021
847
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 = 2e5;
  5.  
  6. int link[N + 1], ds[N + 1], idx[N + 1];
  7.  
  8. int main(){
  9.  
  10.     int nDoor, Q;
  11.     scanf("%d%d", &nDoor, &Q);
  12.     for(int i = 1; i <= nDoor; ++i){
  13.         scanf("%d", &link[i]);
  14.     }
  15.  
  16.     for(int i = 1; i <= nDoor; ++i){
  17.         if(ds[i] == 0){
  18.             ds[i] = i;
  19.             idx[i] = 0;
  20.             int cnt = 1;
  21.             for(int j = link[i]; j != i; j = link[j]){
  22.                 ds[j] = i;
  23.                 idx[j] = cnt++;
  24.             }
  25.         }
  26.     }
  27.  
  28.     for(int q = 1; q <= Q; ++q){
  29.         int st, ed, a, b;
  30.         scanf("%d%d%d%d", &st, &ed, &a, &b);
  31.         if(ds[a] == ds[b]){
  32.             if(ds[st] != ds[ed]){
  33.                 cout << "SURVIVE\n";
  34.             } else if(ds[st] != ds[a]){
  35.                 cout << "DEAD\n";
  36.             } else {
  37.                 if(idx[b] < idx[a]){
  38.                     swap(a, b);
  39.                 }
  40.                 bool stInFSet = idx[st] > idx[a] && idx[st] <= idx[b];
  41.                 bool edInFSet = idx[ed] > idx[a] && idx[ed] <= idx[b];
  42.                 if(stInFSet == edInFSet){
  43.                     cout << "DEAD\n";
  44.                 } else {
  45.                     cout << "SURVIVE\n";
  46.                 }
  47.             }
  48.         } else {
  49.             bool stInNewSet = ds[st] == ds[a] || ds[st] == ds[b];
  50.             bool edInNewSet = ds[ed] == ds[a] || ds[ed] == ds[b];
  51.             if(stInNewSet && edInNewSet || ds[st] == ds[ed]){
  52.                 cout << "DEAD\n";
  53.             } else {
  54.                 cout << "SURVIVE\n";
  55.             }
  56.         }
  57.     }
  58.  
  59.     return 0;
  60. }
  61.  
RAW Paste Data