oj.uz

Submission #580592

# Submission time Handle Problem Language Result Execution time Memory
580592 2022-06-21T13:15:32 Z Vanilla Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 51148 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;
				}
			}
			while (l <= r) {
				int mid = (l + r) / 2;
				if (query0(mid, n2) >= S[i]) {
					f2 = mid;
					r = mid - 1;
				}
				else {
					l = mid + 1;
				}
			}
			l = n1, r = n2, f2 = -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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4948 KB Output is correct
2 Correct 4 ms 4920 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5012 KB Output is correct
7 Correct 3 ms 4948 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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4948 KB Output is correct
2 Correct 4 ms 4920 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5012 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 243 ms 5288 KB Output is correct
11 Correct 145 ms 5232 KB Output is correct
12 Correct 15 ms 5336 KB Output is correct
13 Correct 260 ms 5284 KB Output is correct
14 Correct 162 ms 5324 KB Output is correct
15 Correct 208 ms 5424 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4042 ms 51148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4948 KB Output is correct
2 Correct 4 ms 4920 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5012 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 243 ms 5288 KB Output is correct
11 Correct 145 ms 5232 KB Output is correct
12 Correct 15 ms 5336 KB Output is correct
13 Correct 260 ms 5284 KB Output is correct
14 Correct 162 ms 5324 KB Output is correct
15 Correct 208 ms 5424 KB Output is correct
16 Execution timed out 4042 ms 51148 KB Time limit exceeded
17 Halted 0 ms 0 KB -