oj.uz

Submission #619489

# Submission time Handle Problem Language Result Execution time Memory
619489 2022-08-02T12:27:17 Z Vanilla Werewolf (IOI18_werewolf) C++17
100 / 100
 835 ms 124020 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 2e5 + 2;
const int lg = 20;
vector <int> ad [maxn];
vector <int> reach [2][maxn];
int dsu [maxn];
int bit [maxn * 2 + 200];
int up [2][maxn][lg];
int in [2][maxn];
int val [2][maxn];
int sz [2][maxn];
int ps = 2;

int dad (int x) {
	return dsu[x] = (x == dsu[x] ? x: dad(dsu[x]));
}

void dfs (int t, int u) {
	in[t][u] = ++ps, sz[t][u] = 1;
	for (int i = 1; i < lg; i++){
		up[t][u][i] = up[t][up[t][u][i-1]][i-1];
	}
	for (int v: reach[t][u]) {
		up[t][v][0] = u;
		dfs(t, v);
		sz[t][u]+=sz[t][v];
	}
}

void add (int x, int y) {
	for (; x < maxn * 2 + 20; x+=x & -x) bit[x]+=y;
}

int query (int x) {
	int rs = 0;
	for (; x; x-=x & -x) rs+=bit[x];
	return rs;
}

struct event {
	int type; // 1 -> start, 2 -> point, 3 -> end
	int x; // OX
	int l; // OY
	int r; // OY		
	int idx;

	inline bool operator < (const event& oth) const {
		if (x == oth.x) return type < oth.type;
		return x < oth.x;
	}
};

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 = L.size();
	vector <int> rs (Q);
	for (int i = 0; i < M; i++){
		ad[X[i]].push_back(Y[i]);
		ad[Y[i]].push_back(X[i]);
	}
	iota (dsu, dsu + maxn, 0);
	for (int i = 0; i < N; i++){
		for (int j: ad[i]) {
			if (j > i) continue;
			if (dad(j) != i) {
				reach[0][i].push_back(dad(j));
				dsu[dad(j)] = i;
			}
		}
	}
	iota (dsu, dsu + maxn, 0);
	for (int i = N - 1; i >= 0; i--) {
		for (int j: ad[i]) {
			if (j < i) continue;
			if (dad(j) != i) {
				reach[1][i].push_back(dad(j));
				dsu[dad(j)] = i;
			}
		}
	}
	up[0][N-1][0] = N-1;
	up[1][0][0] = 0;
	dfs(0, N - 1);
	ps = 2;
	dfs(1, 0);
	for (int i = 0; i < Q; i++){
		for (int j = lg - 1; j >= 0; j--){
			if (up[1][S[i]][j] >= L[i]) S[i] = up[1][S[i]][j];
			if (up[0][E[i]][j] <= R[i]) E[i] = up[0][E[i]][j];
		}
	}
	vector <event> ev;
	for (int i = 0; i < N; i++){
		ev.push_back({2, in[1][i], in[0][i], in[0][i], i});
	}
	for (int i = 0; i < Q; i++){
		ev.push_back({1, in[1][S[i]], 					in[0][E[i]], in[0][E[i]] + sz[0][E[i]] - 1, i});
		ev.push_back({3, in[1][S[i]] + sz[1][S[i]] - 1, in[0][E[i]], in[0][E[i]] + sz[0][E[i]] - 1, i});
	}
	sort(ev.begin(), ev.end());
	for (auto& [t, x, l, r, id]: ev) {
		if (t == 1) {
			rs[id] -= query(r) - query(l - 1);
		}
		else if (t == 2) {
			add(l, 1);
		}
		else {
			rs[id] += query(r) - query(l - 1);
		}
	}
	for (int i = 0; i < Q; i++){
		rs[i] = !!rs[i];
	}
	return rs;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15316 KB Output is correct
2 Correct 8 ms 15188 KB Output is correct
3 Correct 7 ms 15188 KB Output is correct
4 Correct 9 ms 15188 KB Output is correct
5 Correct 8 ms 15188 KB Output is correct
6 Correct 9 ms 15188 KB Output is correct
7 Correct 8 ms 15296 KB Output is correct
8 Correct 11 ms 15188 KB Output is correct
9 Correct 9 ms 15292 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15316 KB Output is correct
2 Correct 8 ms 15188 KB Output is correct
3 Correct 7 ms 15188 KB Output is correct
4 Correct 9 ms 15188 KB Output is correct
5 Correct 8 ms 15188 KB Output is correct
6 Correct 9 ms 15188 KB Output is correct
7 Correct 8 ms 15296 KB Output is correct
8 Correct 11 ms 15188 KB Output is correct
9 Correct 9 ms 15292 KB Output is correct
10 Correct 14 ms 16704 KB Output is correct
11 Correct 14 ms 16696 KB Output is correct
12 Correct 14 ms 16560 KB Output is correct
13 Correct 14 ms 16948 KB Output is correct
14 Correct 16 ms 16940 KB Output is correct
15 Correct 18 ms 16820 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 99012 KB Output is correct
2 Correct 625 ms 110372 KB Output is correct
3 Correct 556 ms 105752 KB Output is correct
4 Correct 720 ms 103928 KB Output is correct
5 Correct 616 ms 103808 KB Output is correct
6 Correct 635 ms 103544 KB Output is correct
7 Correct 605 ms 103440 KB Output is correct
8 Correct 700 ms 110496 KB Output is correct
9 Correct 658 ms 105756 KB Output is correct
10 Correct 580 ms 103952 KB Output is correct
11 Correct 567 ms 103812 KB Output is correct
12 Correct 668 ms 103584 KB Output is correct
13 Correct 734 ms 116984 KB Output is correct
14 Correct 690 ms 117016 KB Output is correct
15 Correct 637 ms 117028 KB Output is correct
16 Correct 641 ms 117124 KB Output is correct
17 Correct 559 ms 103420 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15316 KB Output is correct
2 Correct 8 ms 15188 KB Output is correct
3 Correct 7 ms 15188 KB Output is correct
4 Correct 9 ms 15188 KB Output is correct
5 Correct 8 ms 15188 KB Output is correct
6 Correct 9 ms 15188 KB Output is correct
7 Correct 8 ms 15296 KB Output is correct
8 Correct 11 ms 15188 KB Output is correct
9 Correct 9 ms 15292 KB Output is correct
10 Correct 14 ms 16704 KB Output is correct
11 Correct 14 ms 16696 KB Output is correct
12 Correct 14 ms 16560 KB Output is correct
13 Correct 14 ms 16948 KB Output is correct
14 Correct 16 ms 16940 KB Output is correct
15 Correct 18 ms 16820 KB Output is correct
16 Correct 569 ms 99012 KB Output is correct
17 Correct 625 ms 110372 KB Output is correct
18 Correct 556 ms 105752 KB Output is correct
19 Correct 720 ms 103928 KB Output is correct
20 Correct 616 ms 103808 KB Output is correct
21 Correct 635 ms 103544 KB Output is correct
22 Correct 605 ms 103440 KB Output is correct
23 Correct 700 ms 110496 KB Output is correct
24 Correct 658 ms 105756 KB Output is correct
25 Correct 580 ms 103952 KB Output is correct
26 Correct 567 ms 103812 KB Output is correct
27 Correct 668 ms 103584 KB Output is correct
28 Correct 734 ms 116984 KB Output is correct
29 Correct 690 ms 117016 KB Output is correct
30 Correct 637 ms 117028 KB Output is correct
31 Correct 641 ms 117124 KB Output is correct
32 Correct 559 ms 103420 KB Output is correct
33 Correct 632 ms 104776 KB Output is correct
34 Correct 316 ms 57240 KB Output is correct
35 Correct 711 ms 109408 KB Output is correct
36 Correct 708 ms 104676 KB Output is correct
37 Correct 727 ms 108108 KB Output is correct
38 Correct 655 ms 105704 KB Output is correct
39 Correct 669 ms 123632 KB Output is correct
40 Correct 835 ms 116356 KB Output is correct
41 Correct 526 ms 107100 KB Output is correct
42 Correct 560 ms 104760 KB Output is correct
43 Correct 708 ms 116132 KB Output is correct
44 Correct 710 ms 108104 KB Output is correct
45 Correct 684 ms 124020 KB Output is correct
46 Correct 584 ms 123672 KB Output is correct
47 Correct 641 ms 117208 KB Output is correct
48 Correct 652 ms 117028 KB Output is correct
49 Correct 664 ms 117168 KB Output is correct
50 Correct 613 ms 117120 KB Output is correct
51 Correct 687 ms 116388 KB Output is correct
52 Correct 704 ms 116372 KB Output is correct