oj.uz

Submission #602139

# Submission time Handle Problem Language Result Execution time Memory
602139 2022-07-22T15:35:43 Z erekle Werewolf (IOI18_werewolf) C++17
34 / 100
 596 ms 55500 KB 
#include "werewolf.h"
#include <queue>
#include <algorithm>

using namespace std;

const int MAX_N = 2e5+1, LG = 19;
int mx[LG][MAX_N], mn[LG][MAX_N];
int getMN(int l, int r) {
  int i = 0, p2 = 1;
  while (p2 <= r-l+1) ++i, p2 <<= 1;
  --i, p2 >>= 1;
  return min(mn[i][l], mn[i][r-p2+1]);
}
int getMX(int l, int r) {
  int i = 0, p2 = 1;
  while (p2 <= r-l+1) ++i, p2 <<= 1;
  --i, p2 >>= 1;
  return max(mx[i][l], mx[i][r-p2+1]);
}

vector<int> check_validity(int N, vector<int> X,  vector<int> Y,
  vector<int> S, vector<int> E,
  vector<int> L, vector<int> R) {
  int M = X.size(), Q = S.size();
  vector<int> A(Q);
  
  // if (N <= 3000 && M <= 6000 && Q <= 3000) { // subtasks 1 and 2
  //   vector<vector<int>> g(N);
  //   for (int i = 0; i < M; ++i) {
  //     g[X[i]].push_back(Y[i]);
  //     g[Y[i]].push_back(X[i]);
  //   }
  //   for (int qq = 0; qq < Q; ++qq) {
  //     int s = S[qq], e = E[qq], l = L[qq], r = R[qq];

  //     // bfs from start as human
  //     vector<bool> canHuman(N);
  //     queue<int> q;
  //     q.push(s), canHuman[s] = true;
  //     while (!q.empty()) {
  //       int x = q.front();
  //       q.pop();
  //       for (int y : g[x]) {
  //         if (!canHuman[y] && y >= l) q.push(y), canHuman[y] = true;
  //       }
  //     }

  //     vector<bool> canWolf(N);
  //     q.push(e), canWolf[e] = true;
  //     while (!q.empty()) {
  //       int x = q.front();
  //       q.pop();
  //       for (int y : g[x]) {
  //         if (!canWolf[y] && y <= r) q.push(y), canWolf[y] = true;
  //       }
  //     }

  //     for (int i = 0; i < N; ++i) {
  //       if (canHuman[i] && canWolf[i] && l <= i && i <= r) A[qq] = 1;
  //     }
  //   }
  // } else { // subtask 3
    // find order for nodes
    vector<vector<int>> g(N);
    for (int i = 0; i < M; ++i) {
      g[X[i]].push_back(Y[i]);
      g[Y[i]].push_back(X[i]);
    }

    int endPoint = 0;
    for (int i = 0; i < N; ++i) {
      if (g[i].size() == 1) {
        endPoint = i;
        break;
      }
    }

    // move from endpoint and mark nodes
    vector<int> id(N);
    id[0] = endPoint;
    for (int i = 1, cur = g[id[0]][0]; i < N; ++i) {
      id[i] = cur;
      cur = g[cur][0] + g[cur][1] - id[i-1];
    }

    vector<int> linePos(N);
    for (int i = 0; i < N; ++i) linePos[id[i]] = i;

    // store range maximums and minimums with sparse table
    for (int i = 0; i < N; ++i) mx[0][i] = mn[0][i] = id[i];
    for (int i = 1, p2 = 1; i < LG; ++i, p2<<=1) {
      for (int j = 0; j < N; ++j) {
        mx[i][j] = max(mx[i-1][j], mx[i-1][j+p2]);
        mn[i][j] = min(mn[i-1][j], mn[i-1][j+p2]);
      }
    }

    for (int qq = 0; qq < Q; ++qq) {
      int s = S[qq], e = E[qq], l = L[qq], r = R[qq];
      s = linePos[s], e = linePos[e];

      if (s < e) {
        // find last H (only allowing humans) after start
        //  (last one > R)
        int left = s-1, right = e; // there is an H on or after left, not right
        while (left+1 < right) {
          int mid = (left + right) / 2;
          if (getMX(mid, e) > r) left = mid;
          else right = mid;
        }
        int lastH = left;

        // find first W (only allowing werewolves) after start
        //  (first one < L)
        left = s, right = e+1; // there is W on or before right, not left
        while (left+1 < right) {
          int mid = (left + right) / 2;
          if (getMN(s, mid) < l) right = mid;
          else left = mid;
        }
        int firstW = right;
        
        if (lastH+1 < firstW) A[qq] = 1;
      } else {
        // find last W (only allowing werewolves) after end
        //  (last one < L)
        int left = e-1, right = s; // there is a W on or after left, not right
        while (left+1 < right) {
          int mid = (left + right) / 2;
          if (getMN(mid, s) < l) left = mid;
          else right = mid;
        }
        int lastW = left;

        // find first H (only allowing humans) after end
        //  (first one > R)
        left = e, right = s+1; // there is an H on or before right, not left
        while (left+1 < right) {
          int mid = (left + right) / 2;
          if (getMX(e, mid) > r) right = mid;
          else left = mid;
        }
        int firstH = right;
        
        if (lastW+1 < firstH) A[qq] = 1;
      }
    }
  // }

  return A;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 54816 KB Output is correct
2 Correct 440 ms 55268 KB Output is correct
3 Correct 500 ms 55244 KB Output is correct
4 Correct 537 ms 55228 KB Output is correct
5 Correct 571 ms 55280 KB Output is correct
6 Correct 592 ms 55344 KB Output is correct
7 Correct 558 ms 55280 KB Output is correct
8 Correct 429 ms 55196 KB Output is correct
9 Correct 303 ms 55220 KB Output is correct
10 Correct 374 ms 55300 KB Output is correct
11 Correct 326 ms 55288 KB Output is correct
12 Correct 364 ms 55280 KB Output is correct
13 Correct 475 ms 55280 KB Output is correct
14 Correct 569 ms 55300 KB Output is correct
15 Correct 520 ms 55300 KB Output is correct
16 Correct 471 ms 55348 KB Output is correct
17 Correct 555 ms 55500 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -