# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
997802 |
2024-06-12T22:52:26 Z |
biank |
Werewolf (IOI18_werewolf) |
C++14 |
|
4000 ms |
60980 KB |
#include <bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
using vi = vector<int>;
const int MAX_N = 2e5 + 9;
vi adj[MAX_N];
void dfs(int u, vi &vis, int L, int R) {
vis[u] = 1;
for (int v : adj[u]) {
if (!vis[v] && L <= v && v <= R) dfs(v, vis, L, R);
}
}
vi brute(int N, vi S, vi E, vi L, vi R) {
int Q = sz(S);
vi ans(Q, 0);
for (int i = 0; i < Q; i++) {
vi human(N, 0), wolf(N, 0);
dfs(S[i], human, L[i], N - 1);
dfs(E[i], wolf, 0, R[i]);
for (int j = 0; j < N; j++) {
if (human[j] && wolf[j]) {
ans[i] = 1;
break;
}
}
}
return ans;
}
const int MAX_K = 20;
pair<int, int> st[MAX_K][MAX_N];
#define op(a, b) {min(a.first, b.first), max(a.second, b.second)}
pair<int, int> query(int l, int r) {
int log = 31 - __builtin_clz(r - l);
return op(st[log][l], st[log][r - (1 << log)]);
}
pair<int, int> range(int N, int pos, int L, int R) {
int lo = -1, hi = pos;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
auto [mini, maxi] = query(mid, pos + 1);
if (L <= mini && maxi <= R) hi = mid;
else lo = mid;
}
int leftPos = hi;
lo = pos, hi = N;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
auto [mini, maxi] = query(pos, mid + 1);
if (L <= mini && maxi <= R) lo = mid;
else hi = mid;
}
int rightPos = lo;
return {leftPos, rightPos};
}
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
int M = sz(X), Q = sz(S);
for (int i = 0; i < M; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
if (N <= 3000 && M <= 6000 && Q <= 3000) return brute(N, S, E, L, R);
vi v, p(N);
for (int i = 0; i < N; i++) {
if (sz(adj[i]) == 1) {
p[i] = sz(v);
v.push_back(i);
break;
}
}
int par = -1;
while (sz(v) < N) {
for (int u : adj[v.back()]) {
if (u != par) {
par = v.back();
p[u] = sz(v);
v.push_back(u);
break;
}
}
}
for (int i = 0; i < N; i++) {
st[0][i] = {v[i], v[i]};
}
for (int i = 0; i < MAX_K - 1; i++) {
for (int j = 0; j < N - (1 << i); j++) {
st[i + 1][j] = op(st[i][j], st[i][j + (1 << i)]);
}
}
vi ans(Q, 0);
for (int i = 0; i < Q; i++) {
auto [a, b] = range(N, p[S[i]], L[i], N - 1);
auto [c, d] = range(N, p[E[i]], 0, R[i]);
for (int t = 0; t < 2; t++) {
if (a <= c && c <= b) ans[i] = 1;
if (a <= d && d <= b) ans[i] = 1;
swap(a, c), swap(b, d);
}
}
return ans;
}
Compilation message
werewolf.cpp: In function 'std::pair<int, int> range(int, int, int, int)':
werewolf.cpp:50:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
50 | auto [mini, maxi] = query(mid, pos + 1);
| ^
werewolf.cpp:58:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
58 | auto [mini, maxi] = query(pos, mid + 1);
| ^
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:102:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
102 | auto [a, b] = range(N, p[S[i]], L[i], N - 1);
| ^
werewolf.cpp:103:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
103 | auto [c, d] = range(N, p[E[i]], 0, R[i]);
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5468 KB |
Output is correct |
2 |
Correct |
1 ms |
5468 KB |
Output is correct |
3 |
Correct |
1 ms |
5468 KB |
Output is correct |
4 |
Correct |
1 ms |
5468 KB |
Output is correct |
5 |
Correct |
2 ms |
5464 KB |
Output is correct |
6 |
Correct |
1 ms |
5468 KB |
Output is correct |
7 |
Correct |
1 ms |
5468 KB |
Output is correct |
8 |
Correct |
1 ms |
5468 KB |
Output is correct |
9 |
Correct |
1 ms |
5468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5468 KB |
Output is correct |
2 |
Correct |
1 ms |
5468 KB |
Output is correct |
3 |
Correct |
1 ms |
5468 KB |
Output is correct |
4 |
Correct |
1 ms |
5468 KB |
Output is correct |
5 |
Correct |
2 ms |
5464 KB |
Output is correct |
6 |
Correct |
1 ms |
5468 KB |
Output is correct |
7 |
Correct |
1 ms |
5468 KB |
Output is correct |
8 |
Correct |
1 ms |
5468 KB |
Output is correct |
9 |
Correct |
1 ms |
5468 KB |
Output is correct |
10 |
Correct |
133 ms |
5724 KB |
Output is correct |
11 |
Correct |
49 ms |
5724 KB |
Output is correct |
12 |
Correct |
15 ms |
5720 KB |
Output is correct |
13 |
Correct |
155 ms |
5720 KB |
Output is correct |
14 |
Correct |
83 ms |
5720 KB |
Output is correct |
15 |
Correct |
161 ms |
5952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
389 ms |
52308 KB |
Output is correct |
2 |
Correct |
378 ms |
60872 KB |
Output is correct |
3 |
Correct |
388 ms |
60744 KB |
Output is correct |
4 |
Correct |
383 ms |
60976 KB |
Output is correct |
5 |
Correct |
356 ms |
60872 KB |
Output is correct |
6 |
Correct |
354 ms |
60868 KB |
Output is correct |
7 |
Correct |
378 ms |
60868 KB |
Output is correct |
8 |
Correct |
362 ms |
60864 KB |
Output is correct |
9 |
Correct |
243 ms |
60752 KB |
Output is correct |
10 |
Correct |
266 ms |
60868 KB |
Output is correct |
11 |
Correct |
319 ms |
60872 KB |
Output is correct |
12 |
Correct |
231 ms |
60872 KB |
Output is correct |
13 |
Correct |
377 ms |
60868 KB |
Output is correct |
14 |
Correct |
372 ms |
60736 KB |
Output is correct |
15 |
Correct |
380 ms |
60868 KB |
Output is correct |
16 |
Correct |
372 ms |
60868 KB |
Output is correct |
17 |
Correct |
390 ms |
60980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5468 KB |
Output is correct |
2 |
Correct |
1 ms |
5468 KB |
Output is correct |
3 |
Correct |
1 ms |
5468 KB |
Output is correct |
4 |
Correct |
1 ms |
5468 KB |
Output is correct |
5 |
Correct |
2 ms |
5464 KB |
Output is correct |
6 |
Correct |
1 ms |
5468 KB |
Output is correct |
7 |
Correct |
1 ms |
5468 KB |
Output is correct |
8 |
Correct |
1 ms |
5468 KB |
Output is correct |
9 |
Correct |
1 ms |
5468 KB |
Output is correct |
10 |
Correct |
133 ms |
5724 KB |
Output is correct |
11 |
Correct |
49 ms |
5724 KB |
Output is correct |
12 |
Correct |
15 ms |
5720 KB |
Output is correct |
13 |
Correct |
155 ms |
5720 KB |
Output is correct |
14 |
Correct |
83 ms |
5720 KB |
Output is correct |
15 |
Correct |
161 ms |
5952 KB |
Output is correct |
16 |
Correct |
389 ms |
52308 KB |
Output is correct |
17 |
Correct |
378 ms |
60872 KB |
Output is correct |
18 |
Correct |
388 ms |
60744 KB |
Output is correct |
19 |
Correct |
383 ms |
60976 KB |
Output is correct |
20 |
Correct |
356 ms |
60872 KB |
Output is correct |
21 |
Correct |
354 ms |
60868 KB |
Output is correct |
22 |
Correct |
378 ms |
60868 KB |
Output is correct |
23 |
Correct |
362 ms |
60864 KB |
Output is correct |
24 |
Correct |
243 ms |
60752 KB |
Output is correct |
25 |
Correct |
266 ms |
60868 KB |
Output is correct |
26 |
Correct |
319 ms |
60872 KB |
Output is correct |
27 |
Correct |
231 ms |
60872 KB |
Output is correct |
28 |
Correct |
377 ms |
60868 KB |
Output is correct |
29 |
Correct |
372 ms |
60736 KB |
Output is correct |
30 |
Correct |
380 ms |
60868 KB |
Output is correct |
31 |
Correct |
372 ms |
60868 KB |
Output is correct |
32 |
Correct |
390 ms |
60980 KB |
Output is correct |
33 |
Execution timed out |
4075 ms |
30572 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |