oj.uz

Submission #580772

# Submission time Handle Problem Language Result Execution time Memory
580772 2022-06-21T19:01:48 Z Vanilla Werewolf (IOI18_werewolf) C++17
15 / 100
 605 ms 59336 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int maxn_12 = 3e3 + 2;
const int maxn_3 = 5e5 + 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;  
}

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][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: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 7 ms 12056 KB Output is correct
2 Correct 7 ms 12048 KB Output is correct
3 Correct 7 ms 12048 KB Output is correct
4 Correct 8 ms 11988 KB Output is correct
5 Correct 7 ms 12044 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 9 ms 11944 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12056 KB Output is correct
2 Correct 7 ms 12048 KB Output is correct
3 Correct 7 ms 12048 KB Output is correct
4 Correct 8 ms 11988 KB Output is correct
5 Correct 7 ms 12044 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 9 ms 11944 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 261 ms 12380 KB Output is correct
11 Correct 135 ms 12244 KB Output is correct
12 Correct 17 ms 12440 KB Output is correct
13 Correct 267 ms 12372 KB Output is correct
14 Correct 174 ms 12332 KB Output is correct
15 Correct 234 ms 12460 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 605 ms 59336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12056 KB Output is correct
2 Correct 7 ms 12048 KB Output is correct
3 Correct 7 ms 12048 KB Output is correct
4 Correct 8 ms 11988 KB Output is correct
5 Correct 7 ms 12044 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 9 ms 11944 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 261 ms 12380 KB Output is correct
11 Correct 135 ms 12244 KB Output is correct
12 Correct 17 ms 12440 KB Output is correct
13 Correct 267 ms 12372 KB Output is correct
14 Correct 174 ms 12332 KB Output is correct
15 Correct 234 ms 12460 KB Output is correct
16 Incorrect 605 ms 59336 KB Output isn't correct
17 Halted 0 ms 0 KB -