oj.uz

Submission #580781

# Submission time Handle Problem Language Result Execution time Memory
580781 2022-06-21T19:37:27 Z Vanilla Werewolf (IOI18_werewolf) C++17
15 / 100
 896 ms 60416 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, sp[1] -> max

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;  
}

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

int query1 (int l, int r) {
  int k = log2(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 (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) {
				int node = i;
				act[node] = 1;
				while (1) {
					for (int v: ad[node]) {
						if (!act[v]) {
							act[v] = act[node] + 1;
							node = v;
							break;
						}
					}
					if (ad[node].size() == 1) break;
				}
				break;
			}
		}
		for (int i = 0; i < N; i++){
			sp[0][act[i]][0] = i;
			sp[1][act[i]][0] = 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[E[i]];
			if (n1 < n2){ 
				int l = n1, r = n2, f1 = -1, f2 = 1e9;
				while (l <= r) {
					int mid = (l + r) / 2;
					if (query0(n1, mid) >= L[i]) {
						f1 = mid;
						l = mid + 1;
					}
					else {
						r = mid - 1;
					}
				}
				l = n1, r = n2;
				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 = 1e9;
				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;
				while (l <= r) {
					int mid = (l + r) / 2;
					if (query0(mid, n2) >= L[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:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for (int i = 0; i < X.size(); i++){
      |                  ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 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 4948 KB Output is correct
7 Correct 4 ms 4896 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 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 4948 KB Output is correct
7 Correct 4 ms 4896 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct
10 Correct 238 ms 5284 KB Output is correct
11 Correct 126 ms 5236 KB Output is correct
12 Correct 13 ms 5332 KB Output is correct
13 Correct 311 ms 5284 KB Output is correct
14 Correct 164 ms 5240 KB Output is correct
15 Correct 223 ms 5420 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 820 ms 51992 KB Output is correct
2 Correct 896 ms 60412 KB Output is correct
3 Incorrect 832 ms 60416 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 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 4948 KB Output is correct
7 Correct 4 ms 4896 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct
10 Correct 238 ms 5284 KB Output is correct
11 Correct 126 ms 5236 KB Output is correct
12 Correct 13 ms 5332 KB Output is correct
13 Correct 311 ms 5284 KB Output is correct
14 Correct 164 ms 5240 KB Output is correct
15 Correct 223 ms 5420 KB Output is correct
16 Correct 820 ms 51992 KB Output is correct
17 Correct 896 ms 60412 KB Output is correct
18 Incorrect 832 ms 60416 KB Output isn't correct
19 Halted 0 ms 0 KB -