# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
851077 |
2023-09-18T13:24:39 Z |
nonono |
Werewolf (IOI18_werewolf) |
C++14 |
|
663 ms |
104772 KB |
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 10;
struct DSU {
vector<int> par;
void init(int n) {
par.resize(n);
for(int i = 0; i < n; i ++) par[i] = i;
}
int get_root(int u) {
return par[u] == u ? u : par[u] = get_root(par[u]);
}
};
struct TGraph {
int root = 0;
vector<vector<int>> adj;
int timer = -1;
vector<int> in, out;
int up[mxN][20];
DSU lnk;
void init(int n) {
adj.resize(n);
in.resize(n);
out.resize(n);
lnk.init(n);
}
void addEdge(int u, int v) {
u = lnk.get_root(u);
v = lnk.get_root(v);
if(u == v) return ;
adj[u].push_back(v);
lnk.par[v] = u;
root = u;
}
void dfs(int u) {
in[u] = ++ timer;
for(int v : adj[u]) {
up[v][0] = u;
dfs(v);
}
out[u] = timer;
}
void build(int n) {
up[root][0] = root;
dfs(root);
for(int k = 1; k <= 18; k ++) {
for(int u = 0; u <= n - 1; u ++) {
up[u][k] = up[up[u][k - 1]][k - 1];
}
}
}
int get(int type, int u, int lim) {
if(type == 0) for(int k = 18; k >= 0; k --) if(up[u][k] >= lim) u = up[u][k];
if(type == 1) for(int k = 18; k >= 0; k --) if(up[u][k] <= lim) u = up[u][k];
return u;
}
};
vector<int> fen;
void update(int i, int x, int N) {
for(i ++ ; i <= N; i += i & (- i)) fen[i] += x;
}
int get(int i) {
int res = 0;
for(i ++ ; i > 0; i -= i & (- i)) res += fen[i];
return res;
}
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 Q = S.size();
int M = X.size();
vector<int> A(Q);
vector<vector<int>> g(N);
vector<vector<pair<int, int>>> k(N);
TGraph tr[2];
vector<int> id(N);
fen.resize(N + 1, 0);
for (int i = 0; i < Q; ++i) {
A[i] = 0;
}
for(int i = 0; i < M; i ++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
tr[0].init(N);
tr[1].init(N);
for(int i = N - 1; i >= 0; i --) for(int j : g[i]) if(i < j) tr[0].addEdge(i, j);
for(int i = 0; i <= N - 1; i ++) for(int j : g[i]) if(i > j) tr[1].addEdge(i, j);
tr[0].build(N);
tr[1].build(N);
for(int i = 0; i <= Q - 1; i ++) {
int u = tr[0].get(0, S[i], L[i]);
E[i] = tr[1].get(1, E[i], R[i]);
k[tr[0].out[u]].push_back({i, 1});
if(tr[0].in[u]) k[tr[0].in[u] - 1].push_back({i, -1});
}
for(int i = 0; i <= N - 1; i ++) id[tr[0].in[i]] = i;
for(int i = 0; i <= N - 1; i ++) {
int x = id[i];
update(tr[1].in[x], 1, N);
for(auto [j, base] : k[i]) {
A[j] += base * (get(tr[1].out[E[j]]) - get(tr[1].in[E[j]] - 1));
}
}
for(int i = 0; i <= Q - 1; i ++) A[i] = A[i] > 0;
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:133:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
133 | for(auto [j, base] : k[i]) {
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
31576 KB |
Output is correct |
2 |
Correct |
16 ms |
31576 KB |
Output is correct |
3 |
Correct |
17 ms |
31576 KB |
Output is correct |
4 |
Correct |
18 ms |
31576 KB |
Output is correct |
5 |
Correct |
17 ms |
31576 KB |
Output is correct |
6 |
Correct |
16 ms |
31576 KB |
Output is correct |
7 |
Correct |
17 ms |
31576 KB |
Output is correct |
8 |
Correct |
18 ms |
31576 KB |
Output is correct |
9 |
Correct |
17 ms |
31580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
31576 KB |
Output is correct |
2 |
Correct |
16 ms |
31576 KB |
Output is correct |
3 |
Correct |
17 ms |
31576 KB |
Output is correct |
4 |
Correct |
18 ms |
31576 KB |
Output is correct |
5 |
Correct |
17 ms |
31576 KB |
Output is correct |
6 |
Correct |
16 ms |
31576 KB |
Output is correct |
7 |
Correct |
17 ms |
31576 KB |
Output is correct |
8 |
Correct |
18 ms |
31576 KB |
Output is correct |
9 |
Correct |
17 ms |
31580 KB |
Output is correct |
10 |
Correct |
20 ms |
32612 KB |
Output is correct |
11 |
Correct |
20 ms |
32600 KB |
Output is correct |
12 |
Correct |
23 ms |
32600 KB |
Output is correct |
13 |
Correct |
20 ms |
32600 KB |
Output is correct |
14 |
Correct |
20 ms |
32856 KB |
Output is correct |
15 |
Correct |
22 ms |
32592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
489 ms |
96176 KB |
Output is correct |
2 |
Correct |
438 ms |
97108 KB |
Output is correct |
3 |
Correct |
400 ms |
95372 KB |
Output is correct |
4 |
Correct |
435 ms |
94536 KB |
Output is correct |
5 |
Correct |
406 ms |
94664 KB |
Output is correct |
6 |
Correct |
440 ms |
95620 KB |
Output is correct |
7 |
Correct |
401 ms |
94516 KB |
Output is correct |
8 |
Correct |
397 ms |
97124 KB |
Output is correct |
9 |
Correct |
322 ms |
94148 KB |
Output is correct |
10 |
Correct |
302 ms |
93960 KB |
Output is correct |
11 |
Correct |
317 ms |
94156 KB |
Output is correct |
12 |
Correct |
344 ms |
93860 KB |
Output is correct |
13 |
Correct |
647 ms |
102468 KB |
Output is correct |
14 |
Correct |
523 ms |
102460 KB |
Output is correct |
15 |
Correct |
633 ms |
102264 KB |
Output is correct |
16 |
Correct |
569 ms |
102344 KB |
Output is correct |
17 |
Correct |
392 ms |
94528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
31576 KB |
Output is correct |
2 |
Correct |
16 ms |
31576 KB |
Output is correct |
3 |
Correct |
17 ms |
31576 KB |
Output is correct |
4 |
Correct |
18 ms |
31576 KB |
Output is correct |
5 |
Correct |
17 ms |
31576 KB |
Output is correct |
6 |
Correct |
16 ms |
31576 KB |
Output is correct |
7 |
Correct |
17 ms |
31576 KB |
Output is correct |
8 |
Correct |
18 ms |
31576 KB |
Output is correct |
9 |
Correct |
17 ms |
31580 KB |
Output is correct |
10 |
Correct |
20 ms |
32612 KB |
Output is correct |
11 |
Correct |
20 ms |
32600 KB |
Output is correct |
12 |
Correct |
23 ms |
32600 KB |
Output is correct |
13 |
Correct |
20 ms |
32600 KB |
Output is correct |
14 |
Correct |
20 ms |
32856 KB |
Output is correct |
15 |
Correct |
22 ms |
32592 KB |
Output is correct |
16 |
Correct |
489 ms |
96176 KB |
Output is correct |
17 |
Correct |
438 ms |
97108 KB |
Output is correct |
18 |
Correct |
400 ms |
95372 KB |
Output is correct |
19 |
Correct |
435 ms |
94536 KB |
Output is correct |
20 |
Correct |
406 ms |
94664 KB |
Output is correct |
21 |
Correct |
440 ms |
95620 KB |
Output is correct |
22 |
Correct |
401 ms |
94516 KB |
Output is correct |
23 |
Correct |
397 ms |
97124 KB |
Output is correct |
24 |
Correct |
322 ms |
94148 KB |
Output is correct |
25 |
Correct |
302 ms |
93960 KB |
Output is correct |
26 |
Correct |
317 ms |
94156 KB |
Output is correct |
27 |
Correct |
344 ms |
93860 KB |
Output is correct |
28 |
Correct |
647 ms |
102468 KB |
Output is correct |
29 |
Correct |
523 ms |
102460 KB |
Output is correct |
30 |
Correct |
633 ms |
102264 KB |
Output is correct |
31 |
Correct |
569 ms |
102344 KB |
Output is correct |
32 |
Correct |
392 ms |
94528 KB |
Output is correct |
33 |
Correct |
479 ms |
96084 KB |
Output is correct |
34 |
Correct |
205 ms |
66508 KB |
Output is correct |
35 |
Correct |
663 ms |
98412 KB |
Output is correct |
36 |
Correct |
493 ms |
96592 KB |
Output is correct |
37 |
Correct |
525 ms |
97636 KB |
Output is correct |
38 |
Correct |
507 ms |
96984 KB |
Output is correct |
39 |
Correct |
542 ms |
103944 KB |
Output is correct |
40 |
Correct |
560 ms |
104772 KB |
Output is correct |
41 |
Correct |
382 ms |
95792 KB |
Output is correct |
42 |
Correct |
352 ms |
94128 KB |
Output is correct |
43 |
Correct |
565 ms |
102876 KB |
Output is correct |
44 |
Correct |
443 ms |
97108 KB |
Output is correct |
45 |
Correct |
388 ms |
102156 KB |
Output is correct |
46 |
Correct |
418 ms |
102224 KB |
Output is correct |
47 |
Correct |
589 ms |
102904 KB |
Output is correct |
48 |
Correct |
547 ms |
102456 KB |
Output is correct |
49 |
Correct |
564 ms |
102508 KB |
Output is correct |
50 |
Correct |
612 ms |
102292 KB |
Output is correct |
51 |
Correct |
531 ms |
104140 KB |
Output is correct |
52 |
Correct |
512 ms |
104016 KB |
Output is correct |