Advertisement
erek1e

IOI '18 - Werewolf (49pts)

Jul 23rd, 2022
959
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.30 KB | None | 0 0
  1. #include "werewolf.h"
  2. #include <queue>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. // SUBTASK 3
  8. const int MAX_N = 2e5+1, LG = 19;
  9. int mx[LG][MAX_N], mn[LG][MAX_N];
  10. int getMN(int l, int r) {
  11.   int i = 0, p2 = 1;
  12.   while (p2 <= r-l+1) ++i, p2 <<= 1;
  13.   --i, p2 >>= 1;
  14.   return min(mn[i][l], mn[i][r-p2+1]);
  15. }
  16. int getMX(int l, int r) {
  17.   int i = 0, p2 = 1;
  18.   while (p2 <= r-l+1) ++i, p2 <<= 1;
  19.   --i, p2 >>= 1;
  20.   return max(mx[i][l], mx[i][r-p2+1]);
  21. }
  22.  
  23. vector<int> check_validity(int N, vector<int> X,  vector<int> Y,
  24.   vector<int> S, vector<int> E,
  25.   vector<int> L, vector<int> R) {
  26.   int M = X.size(), Q = S.size();
  27.   vector<int> A(Q);
  28.  
  29.   if (N <= 3000 && M <= 6000 && Q <= 3000) { // subtasks 1 and 2
  30.     vector<vector<int>> g(N);
  31.     for (int i = 0; i < M; ++i) {
  32.       g[X[i]].push_back(Y[i]);
  33.       g[Y[i]].push_back(X[i]);
  34.     }
  35.     for (int qq = 0; qq < Q; ++qq) {
  36.       int s = S[qq], e = E[qq], l = L[qq], r = R[qq];
  37.  
  38.       // bfs from start as human
  39.       vector<bool> canHuman(N);
  40.       queue<int> q;
  41.       q.push(s), canHuman[s] = true;
  42.       while (!q.empty()) {
  43.         int x = q.front();
  44.         q.pop();
  45.         for (int y : g[x]) {
  46.           if (!canHuman[y] && y >= l) q.push(y), canHuman[y] = true;
  47.         }
  48.       }
  49.  
  50.       vector<bool> canWolf(N);
  51.       q.push(e), canWolf[e] = true;
  52.       while (!q.empty()) {
  53.         int x = q.front();
  54.         q.pop();
  55.         for (int y : g[x]) {
  56.           if (!canWolf[y] && y <= r) q.push(y), canWolf[y] = true;
  57.         }
  58.       }
  59.  
  60.       for (int i = 0; i < N; ++i) {
  61.         if (canHuman[i] && canWolf[i] && l <= i && i <= r) A[qq] = 1;
  62.       }
  63.     }
  64.   } else { // subtask 3
  65.     // find order for nodes
  66.     vector<vector<int>> g(N);
  67.     for (int i = 0; i < M; ++i) {
  68.       g[X[i]].push_back(Y[i]);
  69.       g[Y[i]].push_back(X[i]);
  70.     }
  71.  
  72.     int endPoint = 0;
  73.     for (int i = 0; i < N; ++i) {
  74.       if (g[i].size() == 1) {
  75.         endPoint = i;
  76.         break;
  77.       }
  78.     }
  79.  
  80.     // move from endpoint and mark nodes
  81.     vector<int> id(N);
  82.     id[0] = endPoint;
  83.     for (int i = 1, cur = g[id[0]][0]; i < N; ++i) {
  84.       id[i] = cur;
  85.       cur = g[cur][0] + g[cur][1] - id[i-1];
  86.     }
  87.  
  88.     vector<int> linePos(N);
  89.     for (int i = 0; i < N; ++i) linePos[id[i]] = i;
  90.  
  91.     // store range maximums and minimums with sparse table
  92.     for (int i = 0; i < N; ++i) mx[0][i] = mn[0][i] = id[i];
  93.     for (int i = 1, p2 = 1; i < LG; ++i, p2<<=1) {
  94.       for (int j = 0; j < N; ++j) {
  95.         mx[i][j] = max(mx[i-1][j], mx[i-1][j+p2]);
  96.         mn[i][j] = min(mn[i-1][j], mn[i-1][j+p2]);
  97.       }
  98.     }
  99.  
  100.     for (int qq = 0; qq < Q; ++qq) {
  101.       int s = S[qq], e = E[qq], l = L[qq], r = R[qq];
  102.       s = linePos[s], e = linePos[e];
  103.  
  104.       if (s < e) {
  105.         // find last H (only allowing humans) after start
  106.         //  (last one > R)
  107.         int left = s-1, right = e; // there is an H on or after left, not right
  108.         while (left+1 < right) {
  109.           int mid = (left + right) / 2;
  110.           if (getMX(mid, e) > r) left = mid;
  111.           else right = mid;
  112.         }
  113.         int lastH = left;
  114.  
  115.         // find first W (only allowing werewolves) after start
  116.         //  (first one < L)
  117.         left = s, right = e+1; // there is W on or before right, not left
  118.         while (left+1 < right) {
  119.           int mid = (left + right) / 2;
  120.           if (getMN(s, mid) < l) right = mid;
  121.           else left = mid;
  122.         }
  123.         int firstW = right;
  124.        
  125.         if (lastH+1 < firstW) A[qq] = 1;
  126.       } else {
  127.         // find last W (only allowing werewolves) after end
  128.         //  (last one < L)
  129.         int left = e-1, right = s; // there is a W on or after left, not right
  130.         while (left+1 < right) {
  131.           int mid = (left + right) / 2;
  132.           if (getMN(mid, s) < l) left = mid;
  133.           else right = mid;
  134.         }
  135.         int lastW = left;
  136.  
  137.         // find first H (only allowing humans) after end
  138.         //  (first one > R)
  139.         left = e, right = s+1; // there is an H on or before right, not left
  140.         while (left+1 < right) {
  141.           int mid = (left + right) / 2;
  142.           if (getMX(e, mid) > r) right = mid;
  143.           else left = mid;
  144.         }
  145.         int firstH = right;
  146.        
  147.         if (lastW+1 < firstH) A[qq] = 1;
  148.       }
  149.     }
  150.   }
  151.  
  152.   return A;
  153. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement