oj.uz

Submission #619497

# Submission time Handle Problem Language Result Execution time Memory
619497 2022-08-02T12:29:55 Z Vanilla Werewolf (IOI18_werewolf) C++17
100 / 100
 690 ms 115428 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; int x; int l; int r;		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 15188 KB Output is correct
2 Correct 10 ms 15188 KB Output is correct
3 Correct 8 ms 15260 KB Output is correct
4 Correct 8 ms 15220 KB Output is correct
5 Correct 8 ms 15224 KB Output is correct
6 Correct 8 ms 15288 KB Output is correct
7 Correct 8 ms 15188 KB Output is correct
8 Correct 7 ms 15188 KB Output is correct
9 Correct 7 ms 15316 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15188 KB Output is correct
2 Correct 10 ms 15188 KB Output is correct
3 Correct 8 ms 15260 KB Output is correct
4 Correct 8 ms 15220 KB Output is correct
5 Correct 8 ms 15224 KB Output is correct
6 Correct 8 ms 15288 KB Output is correct
7 Correct 8 ms 15188 KB Output is correct
8 Correct 7 ms 15188 KB Output is correct
9 Correct 7 ms 15316 KB Output is correct
10 Correct 13 ms 16564 KB Output is correct
11 Correct 18 ms 16588 KB Output is correct
12 Correct 16 ms 16564 KB Output is correct
13 Correct 16 ms 16800 KB Output is correct
14 Correct 17 ms 16772 KB Output is correct
15 Correct 14 ms 16584 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 95052 KB Output is correct
2 Correct 528 ms 101940 KB Output is correct
3 Correct 495 ms 97540 KB Output is correct
4 Correct 497 ms 95588 KB Output is correct
5 Correct 467 ms 95372 KB Output is correct
6 Correct 525 ms 95144 KB Output is correct
7 Correct 511 ms 95016 KB Output is correct
8 Correct 523 ms 102016 KB Output is correct
9 Correct 466 ms 97408 KB Output is correct
10 Correct 444 ms 95604 KB Output is correct
11 Correct 425 ms 95356 KB Output is correct
12 Correct 520 ms 95136 KB Output is correct
13 Correct 568 ms 108596 KB Output is correct
14 Correct 574 ms 108648 KB Output is correct
15 Correct 540 ms 108696 KB Output is correct
16 Correct 575 ms 108644 KB Output is correct
17 Correct 527 ms 95024 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15188 KB Output is correct
2 Correct 10 ms 15188 KB Output is correct
3 Correct 8 ms 15260 KB Output is correct
4 Correct 8 ms 15220 KB Output is correct
5 Correct 8 ms 15224 KB Output is correct
6 Correct 8 ms 15288 KB Output is correct
7 Correct 8 ms 15188 KB Output is correct
8 Correct 7 ms 15188 KB Output is correct
9 Correct 7 ms 15316 KB Output is correct
10 Correct 13 ms 16564 KB Output is correct
11 Correct 18 ms 16588 KB Output is correct
12 Correct 16 ms 16564 KB Output is correct
13 Correct 16 ms 16800 KB Output is correct
14 Correct 17 ms 16772 KB Output is correct
15 Correct 14 ms 16584 KB Output is correct
16 Correct 523 ms 95052 KB Output is correct
17 Correct 528 ms 101940 KB Output is correct
18 Correct 495 ms 97540 KB Output is correct
19 Correct 497 ms 95588 KB Output is correct
20 Correct 467 ms 95372 KB Output is correct
21 Correct 525 ms 95144 KB Output is correct
22 Correct 511 ms 95016 KB Output is correct
23 Correct 523 ms 102016 KB Output is correct
24 Correct 466 ms 97408 KB Output is correct
25 Correct 444 ms 95604 KB Output is correct
26 Correct 425 ms 95356 KB Output is correct
27 Correct 520 ms 95136 KB Output is correct
28 Correct 568 ms 108596 KB Output is correct
29 Correct 574 ms 108648 KB Output is correct
30 Correct 540 ms 108696 KB Output is correct
31 Correct 575 ms 108644 KB Output is correct
32 Correct 527 ms 95024 KB Output is correct
33 Correct 560 ms 96292 KB Output is correct
34 Correct 295 ms 45624 KB Output is correct
35 Correct 595 ms 100676 KB Output is correct
36 Correct 533 ms 96184 KB Output is correct
37 Correct 610 ms 99548 KB Output is correct
38 Correct 578 ms 97124 KB Output is correct
39 Correct 556 ms 115216 KB Output is correct
40 Correct 689 ms 104920 KB Output is correct
41 Correct 554 ms 98708 KB Output is correct
42 Correct 492 ms 96240 KB Output is correct
43 Correct 662 ms 106188 KB Output is correct
44 Correct 542 ms 99480 KB Output is correct
45 Correct 528 ms 115428 KB Output is correct
46 Correct 538 ms 115212 KB Output is correct
47 Correct 580 ms 108696 KB Output is correct
48 Correct 557 ms 108592 KB Output is correct
49 Correct 587 ms 108676 KB Output is correct
50 Correct 564 ms 108620 KB Output is correct
51 Correct 690 ms 105088 KB Output is correct
52 Correct 663 ms 104868 KB Output is correct