# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
100485 |
2019-03-11T15:10:37 Z |
jeff |
Werewolf (IOI18_werewolf) |
C++14 |
|
1265 ms |
100064 KB |
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
int N, A[800000], id[400000], f[200000], l[2][2][400000], y, z;
pair<int, int> B[800000];
vector<int> adj[2][400000], rs;
vector<pair<int, int> > v;
vector<tuple<int, int, int, int, int> > qr;
inline int frt(int i) {return i == id[i] ? i : id[i] = frt(id[i]);}
inline void ufds(int t, int a, int b) {
a = frt(a);
b = frt(b);
if (a == b) return;
adj[t][a].push_back(y);
adj[t][b].push_back(y);
adj[t][y].push_back(a);
adj[t][y].push_back(b);
id[a] = id[b] = y++;
}
void it(int t, int i, int o) {
l[t][0][i] = z;
for (int j = 0; j < adj[t][i].size(); ++j) if (o != adj[t][i][j]) it(t, adj[t][i][j], i);
if (i < N) {
if (!t) f[z++] = i;
else ++z;
}
l[t][1][i] = z - 1;
}
void init(int i, int a, int b) {
A[i] = INT_MAX;
B[i] = make_pair(a, b);
if (a >= b) return;
init(i * 2, a, (a + b) / 2);
init(i * 2 + 1, (a + b) / 2 + 1, b);
}
int q(int i, int a, int b) {
if (b < B[i].first || B[i].second < a) return INT_MAX;
if (a <= B[i].first && B[i].second <= b) return A[i];
return min(q(i * 2, a, b), q(i * 2 + 1, a, b));
}
void u(int i, int p, int v) {
if (p < B[i].first || B[i].second < p) return;
if (p <= B[i].first && B[i].second <= p) {A[i] = v; return;}
u(i * 2, p, v);
u(i * 2 + 1, p, v);
A[i] = min(A[i * 2], A[i * 2 + 1]);
}
vector<int> check_validity(int _N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
N = _N;
int M = X.size(), Q = S.size(), i, j;
rs.assign(Q, 0);
for (i = 0; i < Q; ++i) qr.emplace_back(R[i], L[i], E[i], S[i], i);
for (i = 0; i < M; ++i) v.emplace_back(max(X[i], Y[i]), min(X[i], Y[i]));
sort(v.begin(), v.end());
sort(qr.begin(), qr.end());
iota(id, id + N * 2 - 1, 0);
y = N;
for (i = j = 0; i < M; ++i) {
while (j < Q && get<0>(qr[j]) < v[i].first) get<2>(qr[j]) = frt(get<2>(qr[j])), swap(get<0>(qr[j]), get<1>(qr[j])), ++j;
ufds(0, v[i].first, v[i].second);
swap(v[i].first, v[i].second);
}
while (j < Q) get<3>(qr[j]) = frt(get<3>(qr[j])), swap(get<0>(qr[j]), get<1>(qr[j])), ++j;
sort(v.begin(), v.end());
sort(qr.begin(), qr.end());
iota(id, id + N * 2 - 1, 0);
y = N;
for (i = M - 1, j = Q - 1; i > -1; --i) {
while (j > -1 && get<0>(qr[j]) > v[i].first) get<3>(qr[j]) = frt(get<3>(qr[j])), --j;
ufds(1, v[i].first, v[i].second);
}
while (j > -1) get<2>(qr[j]) = frt(get<2>(qr[j])), --j;
it(0, N * 2 - 2, -1);
z = 0;
it(1, N * 2 - 2, -1);
for (i = 0; i < Q; ++i) get<0>(qr[i]) = l[0][0][get<2>(qr[i])], get<1>(qr[i]) = l[0][1][get<2>(qr[i])];
sort(qr.begin(), qr.end());
init(1, 0, N - 1);
for (i = Q - 1, j = N - 1; i > -1; --i) {
while (j >= get<0>(qr[i])) u(1, l[1][0][f[j]], j), --j;
rs[get<4>(qr[i])] = q(1, l[1][0][get<3>(qr[i])], l[1][1][get<3>(qr[i])]) <= get<1>(qr[i]);
}
return rs;
}
Compilation message
werewolf.cpp: In function 'void it(int, int, int)':
werewolf.cpp:26:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < adj[t][i].size(); ++j) if (o != adj[t][i][j]) it(t, adj[t][i][j], i);
~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
19200 KB |
Output is correct |
2 |
Correct |
24 ms |
19200 KB |
Output is correct |
3 |
Correct |
23 ms |
19200 KB |
Output is correct |
4 |
Correct |
21 ms |
19192 KB |
Output is correct |
5 |
Correct |
24 ms |
19192 KB |
Output is correct |
6 |
Correct |
22 ms |
19200 KB |
Output is correct |
7 |
Correct |
20 ms |
19200 KB |
Output is correct |
8 |
Correct |
21 ms |
19200 KB |
Output is correct |
9 |
Correct |
23 ms |
19328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
19200 KB |
Output is correct |
2 |
Correct |
24 ms |
19200 KB |
Output is correct |
3 |
Correct |
23 ms |
19200 KB |
Output is correct |
4 |
Correct |
21 ms |
19192 KB |
Output is correct |
5 |
Correct |
24 ms |
19192 KB |
Output is correct |
6 |
Correct |
22 ms |
19200 KB |
Output is correct |
7 |
Correct |
20 ms |
19200 KB |
Output is correct |
8 |
Correct |
21 ms |
19200 KB |
Output is correct |
9 |
Correct |
23 ms |
19328 KB |
Output is correct |
10 |
Correct |
28 ms |
20088 KB |
Output is correct |
11 |
Correct |
30 ms |
20096 KB |
Output is correct |
12 |
Correct |
29 ms |
19960 KB |
Output is correct |
13 |
Correct |
28 ms |
20344 KB |
Output is correct |
14 |
Correct |
31 ms |
20224 KB |
Output is correct |
15 |
Correct |
29 ms |
20088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1168 ms |
75488 KB |
Output is correct |
2 |
Correct |
771 ms |
85344 KB |
Output is correct |
3 |
Correct |
748 ms |
80244 KB |
Output is correct |
4 |
Correct |
803 ms |
77956 KB |
Output is correct |
5 |
Correct |
871 ms |
77824 KB |
Output is correct |
6 |
Correct |
950 ms |
77560 KB |
Output is correct |
7 |
Correct |
1087 ms |
77276 KB |
Output is correct |
8 |
Correct |
700 ms |
85180 KB |
Output is correct |
9 |
Correct |
663 ms |
80172 KB |
Output is correct |
10 |
Correct |
791 ms |
77916 KB |
Output is correct |
11 |
Correct |
817 ms |
77664 KB |
Output is correct |
12 |
Correct |
802 ms |
77408 KB |
Output is correct |
13 |
Correct |
690 ms |
85312 KB |
Output is correct |
14 |
Correct |
642 ms |
85216 KB |
Output is correct |
15 |
Correct |
624 ms |
85340 KB |
Output is correct |
16 |
Correct |
858 ms |
85340 KB |
Output is correct |
17 |
Correct |
1079 ms |
77408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
19200 KB |
Output is correct |
2 |
Correct |
24 ms |
19200 KB |
Output is correct |
3 |
Correct |
23 ms |
19200 KB |
Output is correct |
4 |
Correct |
21 ms |
19192 KB |
Output is correct |
5 |
Correct |
24 ms |
19192 KB |
Output is correct |
6 |
Correct |
22 ms |
19200 KB |
Output is correct |
7 |
Correct |
20 ms |
19200 KB |
Output is correct |
8 |
Correct |
21 ms |
19200 KB |
Output is correct |
9 |
Correct |
23 ms |
19328 KB |
Output is correct |
10 |
Correct |
28 ms |
20088 KB |
Output is correct |
11 |
Correct |
30 ms |
20096 KB |
Output is correct |
12 |
Correct |
29 ms |
19960 KB |
Output is correct |
13 |
Correct |
28 ms |
20344 KB |
Output is correct |
14 |
Correct |
31 ms |
20224 KB |
Output is correct |
15 |
Correct |
29 ms |
20088 KB |
Output is correct |
16 |
Correct |
1168 ms |
75488 KB |
Output is correct |
17 |
Correct |
771 ms |
85344 KB |
Output is correct |
18 |
Correct |
748 ms |
80244 KB |
Output is correct |
19 |
Correct |
803 ms |
77956 KB |
Output is correct |
20 |
Correct |
871 ms |
77824 KB |
Output is correct |
21 |
Correct |
950 ms |
77560 KB |
Output is correct |
22 |
Correct |
1087 ms |
77276 KB |
Output is correct |
23 |
Correct |
700 ms |
85180 KB |
Output is correct |
24 |
Correct |
663 ms |
80172 KB |
Output is correct |
25 |
Correct |
791 ms |
77916 KB |
Output is correct |
26 |
Correct |
817 ms |
77664 KB |
Output is correct |
27 |
Correct |
802 ms |
77408 KB |
Output is correct |
28 |
Correct |
690 ms |
85312 KB |
Output is correct |
29 |
Correct |
642 ms |
85216 KB |
Output is correct |
30 |
Correct |
624 ms |
85340 KB |
Output is correct |
31 |
Correct |
858 ms |
85340 KB |
Output is correct |
32 |
Correct |
1079 ms |
77408 KB |
Output is correct |
33 |
Correct |
1265 ms |
79328 KB |
Output is correct |
34 |
Correct |
517 ms |
55616 KB |
Output is correct |
35 |
Correct |
1094 ms |
91100 KB |
Output is correct |
36 |
Correct |
1059 ms |
85212 KB |
Output is correct |
37 |
Correct |
1174 ms |
89976 KB |
Output is correct |
38 |
Correct |
1128 ms |
86272 KB |
Output is correct |
39 |
Correct |
1006 ms |
99692 KB |
Output is correct |
40 |
Correct |
1126 ms |
95816 KB |
Output is correct |
41 |
Correct |
1066 ms |
88668 KB |
Output is correct |
42 |
Correct |
998 ms |
85160 KB |
Output is correct |
43 |
Correct |
1164 ms |
96196 KB |
Output is correct |
44 |
Correct |
1105 ms |
89840 KB |
Output is correct |
45 |
Correct |
991 ms |
100064 KB |
Output is correct |
46 |
Correct |
929 ms |
99776 KB |
Output is correct |
47 |
Correct |
699 ms |
92000 KB |
Output is correct |
48 |
Correct |
769 ms |
91868 KB |
Output is correct |
49 |
Correct |
752 ms |
91872 KB |
Output is correct |
50 |
Correct |
757 ms |
91868 KB |
Output is correct |
51 |
Correct |
931 ms |
96232 KB |
Output is correct |
52 |
Correct |
926 ms |
96240 KB |
Output is correct |