oj.uz

답안 #580593

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
580593 2022-06-21T13:17:41 Z Vanilla 늑대인간 (IOI18_werewolf) C++17
15 / 100
 4000 ms 51196 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int maxn_12 = 3e3 + 2;
const int maxn_3 = 2e5 + 2;
const int lg = 19;
vector <int> ad [maxn_3];
bitset <maxn_12> vis1, vis2;
int act[maxn_3];
int sp[2][maxn_3][lg]; // sp[0] -> min r, sp[1] -> max l

void dfs1 (int u, int l, int r) {
  vis1[u] = 1;
  for (int v: ad[u]) {
    if (v < l || vis1[v]) continue;
    dfs1(v, l, r);
  }
}

int dfs2 (int u, int l, int r) {
  vis2[u] = 1;
  bool b = (vis1[u]);
  for (int v: ad[u]) {
    if (v > r || vis2[v]) continue;
    b|=dfs2(v, l, r);
  }
  return b;  
}

void label (int u, int p, int nr) {
  act[u] = nr;
  for (int v: ad[u]) {
    if (v == p) continue;
    label(v, u, nr + 1);
  }
}

int query0 (int l, int r) {
  int k = 31 - __builtin_clz(r - l + 1);
  return min(sp[0][l][k], sp[0][r - (1 << k) + 1][k]);
}

int query1 (int l, int r) {
  int k = 31 - __builtin_clz(r - l + 1);
  return max(sp[1][l][k], sp[1][r - (1 << k) + 1][k]);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
  for (int i = 0; i < X.size(); i++){
    ad[X[i]].push_back(Y[i]);
    ad[Y[i]].push_back(X[i]);
  }
  int Q = S.size();
  vector<int> A(Q);
//   if (0){
  if (N <= 3000 && Q <= 3000 && X.size() <= 6000){
    for (int i = 0; i < Q; ++i) {
      vis1 = vis2 = 0;
      dfs1(S[i], L[i], R[i]);
      A[i] = dfs2(E[i], L[i], R[i]);
    }
  }
  else {
    for (int i = 0; i < N; i++){
      if (ad[i].size() == 1) {
        label(i, -1, 0);
		break;
      }
      for (int i = 0; i < N; i++){
        sp[0][i][0] = R[act[i]];
        sp[1][i][0] = L[act[i]];
      }
      for (int k = 1; k < lg; k++){
        for (int i = 0; i + (1 << k) - 1 < N; i++){
          sp[0][i][k] = min(sp[0][i][k-1], sp[0][i + (1 << (k - 1))][k-1]);
          sp[1][i][k] = max(sp[1][i][k-1], sp[1][i + (1 << (k - 1))][k-1]);
        }
      }
    }
	for (int i = 0; i < Q; ++i) {
		int n1 = act[S[i]], n2 = act[R[i]];
		if (n1 < n2){ 
			int l = n1, r = n2, f1 = -1, f2 = -1;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (query0(n1, mid) >= S[i]) {
					f1 = mid;
					l = mid + 1;
				}
				else {
					r = mid - 1;
				}
			}
			l = n1, r = n2, f2 = -1;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (query1(mid, n2) <= R[i]) {
					f2 = mid;
					r = mid - 1;
				}
				else {
					l = mid + 1;
				}
			}
			A[i] = (f1 >= f2);
		}
		else {
			// swap(n1, n2);
			int l = n1, r = n2, f1 = -1, f2 = -1;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (query1(n1, mid) <= R[i]) {
					f1 = mid;
					l = mid + 1;
				}
				else {
					r = mid - 1;
				}
			}
			l = n1, r = n2, f2 = -1;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (query0(mid, n2) >= S[i]) {
					f2 = mid;
					r = mid - 1;
				}
				else {
					l = mid + 1;
				}
			}
			A[i] = (f1 >= f2);
		}
		
    }
  }
  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:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for (int i = 0; i < X.size(); i++){
      |                   ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5020 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 5016 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5020 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 5016 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 230 ms 5292 KB Output is correct
11 Correct 131 ms 5240 KB Output is correct
12 Correct 12 ms 5332 KB Output is correct
13 Correct 258 ms 5280 KB Output is correct
14 Correct 164 ms 5232 KB Output is correct
15 Correct 205 ms 5416 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4051 ms 51196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5020 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 5016 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 230 ms 5292 KB Output is correct
11 Correct 131 ms 5240 KB Output is correct
12 Correct 12 ms 5332 KB Output is correct
13 Correct 258 ms 5280 KB Output is correct
14 Correct 164 ms 5232 KB Output is correct
15 Correct 205 ms 5416 KB Output is correct
16 Execution timed out 4051 ms 51196 KB Time limit exceeded
17 Halted 0 ms 0 KB -