oj.uz

답안 #602127

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
602127 2022-07-22T15:18:30 Z erekle 늑대인간 (IOI18_werewolf) C++17
0 / 100
 987 ms 60332 KB 
#include "werewolf.h"
#include <queue>
#include <iostream>

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];
    }
    for (int i : id) cerr << i << ' '; cerr << endl;

    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 (getMX(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 (getMN(e, mid) < l) right = mid;
          else left = mid;
        }
        int firstH = right;

        if (lastW+1 < firstH) A[qq] = 1;
      }
    }
  // }

  return A;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:86:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   86 |     for (int i : id) cerr << i << ' '; cerr << endl;
      |     ^~~
werewolf.cpp:86:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   86 |     for (int i : id) cerr << i << ' '; cerr << endl;
      |                                        ^~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 987 ms 60332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -