# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
82794 |
2018-11-01T17:53:57 Z |
zubec |
Werewolf (IOI18_werewolf) |
C++14 |
|
1254 ms |
272724 KB |
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200100;
vector <vector <int> > g, g1, g2;
int a[N], pos[N], n, dsu[2][N], up[2][20][N], tiktak, tin[2][N], tout[2][N], fenw[N];
int dsu_get(int v, int p){
if (v == dsu[p][v])
return v;
return dsu[p][v] = dsu_get(dsu[p][v], p);
}
void dfs(vector <vector <int> > &g, int cur, int v, int p){
up[cur][0][v] = p;
for (int i = 1; i < 20; i++)
up[cur][i][v] = up[cur][i-1][up[cur][i-1][v]];
tin[cur][v] = ++tiktak;
for (int i = 0; i < g[v].size(); i++){
int to = g[v][i];
dfs(g, cur, to, v);
}
tout[cur][v] = tiktak;
}
void upd(int v){
for (int i = v; i <= n; i+=(i & (-i))){
++fenw[i];
}
}
int get(int v){
int ans = 0;
for (int i = v; i >= 1; i-=(i & (-i)))
ans += fenw[i];
return ans;
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) {
n = N;
for (int i = 0; i <= n; i++){
dsu[0][i] = dsu[1][i] = i;
fenw[i] = 0;
}
g.resize(n);
g1.resize(n);
g2.resize(n);
vector <int> A((int)S.size());
for (int i = 0; i < X.size(); i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
for (int i = n-1; i >= 0; i--){
for (int j = 0; j < g[i].size(); j++){
int to = g[i][j];
if (i > to)
continue;
int a = dsu_get(i, 0);
int b = dsu_get(to, 0);
if (a == b)
continue;
dsu[0][b] = a;
g1[a].push_back(b);
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < g[i].size(); j++){
int to = g[i][j];
if (i < to)
continue;
int a = dsu_get(i, 1);
int b = dsu_get(to, 1);
if (a == b)
continue;
dsu[1][b] = a;
g2[a].push_back(b);
}
}
tiktak = 0;
dfs(g1, 0, dsu_get(0, 0), dsu_get(0, 0));
tiktak = 0;
dfs(g2, 1, dsu_get(0, 1), dsu_get(0, 1));
//return A;
vector <pair<int, pair<int, int> > > zapr;
for (int i = 0; i < S.size(); i++){
int s = S[i], e = E[i], l = L[i], r = R[i];
for (int i = 19; i >= 0; i--){
if (up[0][i][s] >= l)
s = up[0][i][s];
if (up[1][i][e] <= r)
e = up[1][i][e];
}
zapr.push_back({tin[0][s]-1, {-(i+1), e}});
zapr.push_back({tout[0][s], {i+1, e}});
}
for (int i = 0; i < n; i++){
pos[tin[0][i]-1] = tin[1][i];
}
sort(zapr.begin(), zapr.end());
int ptr = 0;
for (int i = 0; i < zapr.size(); i++){
int curTim = zapr[i].first, id = zapr[i].second.first, v = zapr[i].second.second;
while(ptr < curTim){
upd(pos[ptr]);
++ptr;
}
if (id < 0){
A[abs(id)-1] -= (get(tout[1][v])-get(tin[1][v]-1));
} else {
A[abs(id)-1] += (get(tout[1][v])-get(tin[1][v]-1));
}
}
for (int i = 0; i < A.size(); i++)
A[i] = (A[i] > 0);
return A;
}
/**
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
Compilation message
werewolf.cpp: In function 'void dfs(std::vector<std::vector<int> >&, int, int, int)':
werewolf.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
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:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < X.size(); i++){
~~^~~~~~~~~~
werewolf.cpp:57:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < g[i].size(); j++){
~~^~~~~~~~~~~~~
werewolf.cpp:70:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < g[i].size(); j++){
~~^~~~~~~~~~~~~
werewolf.cpp:88:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < S.size(); i++){
~~^~~~~~~~~~
werewolf.cpp:104:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < zapr.size(); i++){
~~^~~~~~~~~~~~~
werewolf.cpp:118:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < A.size(); i++)
~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
636 KB |
Output is correct |
2 |
Correct |
2 ms |
636 KB |
Output is correct |
3 |
Correct |
2 ms |
700 KB |
Output is correct |
4 |
Correct |
2 ms |
700 KB |
Output is correct |
5 |
Correct |
2 ms |
712 KB |
Output is correct |
6 |
Correct |
3 ms |
712 KB |
Output is correct |
7 |
Correct |
2 ms |
716 KB |
Output is correct |
8 |
Correct |
2 ms |
720 KB |
Output is correct |
9 |
Correct |
3 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
636 KB |
Output is correct |
2 |
Correct |
2 ms |
636 KB |
Output is correct |
3 |
Correct |
2 ms |
700 KB |
Output is correct |
4 |
Correct |
2 ms |
700 KB |
Output is correct |
5 |
Correct |
2 ms |
712 KB |
Output is correct |
6 |
Correct |
3 ms |
712 KB |
Output is correct |
7 |
Correct |
2 ms |
716 KB |
Output is correct |
8 |
Correct |
2 ms |
720 KB |
Output is correct |
9 |
Correct |
3 ms |
724 KB |
Output is correct |
10 |
Correct |
9 ms |
2396 KB |
Output is correct |
11 |
Correct |
9 ms |
2476 KB |
Output is correct |
12 |
Correct |
9 ms |
2476 KB |
Output is correct |
13 |
Correct |
9 ms |
2848 KB |
Output is correct |
14 |
Correct |
13 ms |
3012 KB |
Output is correct |
15 |
Correct |
16 ms |
3076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1254 ms |
83428 KB |
Output is correct |
2 |
Correct |
976 ms |
89244 KB |
Output is correct |
3 |
Correct |
953 ms |
89244 KB |
Output is correct |
4 |
Correct |
1103 ms |
89244 KB |
Output is correct |
5 |
Correct |
967 ms |
89244 KB |
Output is correct |
6 |
Correct |
1150 ms |
89244 KB |
Output is correct |
7 |
Correct |
1150 ms |
89244 KB |
Output is correct |
8 |
Correct |
884 ms |
89268 KB |
Output is correct |
9 |
Correct |
624 ms |
89268 KB |
Output is correct |
10 |
Correct |
612 ms |
89268 KB |
Output is correct |
11 |
Correct |
626 ms |
89268 KB |
Output is correct |
12 |
Correct |
699 ms |
89268 KB |
Output is correct |
13 |
Correct |
990 ms |
95424 KB |
Output is correct |
14 |
Correct |
1066 ms |
95424 KB |
Output is correct |
15 |
Correct |
1056 ms |
95432 KB |
Output is correct |
16 |
Correct |
970 ms |
95464 KB |
Output is correct |
17 |
Correct |
1163 ms |
95464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
636 KB |
Output is correct |
2 |
Correct |
2 ms |
636 KB |
Output is correct |
3 |
Correct |
2 ms |
700 KB |
Output is correct |
4 |
Correct |
2 ms |
700 KB |
Output is correct |
5 |
Correct |
2 ms |
712 KB |
Output is correct |
6 |
Correct |
3 ms |
712 KB |
Output is correct |
7 |
Correct |
2 ms |
716 KB |
Output is correct |
8 |
Correct |
2 ms |
720 KB |
Output is correct |
9 |
Correct |
3 ms |
724 KB |
Output is correct |
10 |
Correct |
9 ms |
2396 KB |
Output is correct |
11 |
Correct |
9 ms |
2476 KB |
Output is correct |
12 |
Correct |
9 ms |
2476 KB |
Output is correct |
13 |
Correct |
9 ms |
2848 KB |
Output is correct |
14 |
Correct |
13 ms |
3012 KB |
Output is correct |
15 |
Correct |
16 ms |
3076 KB |
Output is correct |
16 |
Correct |
1254 ms |
83428 KB |
Output is correct |
17 |
Correct |
976 ms |
89244 KB |
Output is correct |
18 |
Correct |
953 ms |
89244 KB |
Output is correct |
19 |
Correct |
1103 ms |
89244 KB |
Output is correct |
20 |
Correct |
967 ms |
89244 KB |
Output is correct |
21 |
Correct |
1150 ms |
89244 KB |
Output is correct |
22 |
Correct |
1150 ms |
89244 KB |
Output is correct |
23 |
Correct |
884 ms |
89268 KB |
Output is correct |
24 |
Correct |
624 ms |
89268 KB |
Output is correct |
25 |
Correct |
612 ms |
89268 KB |
Output is correct |
26 |
Correct |
626 ms |
89268 KB |
Output is correct |
27 |
Correct |
699 ms |
89268 KB |
Output is correct |
28 |
Correct |
990 ms |
95424 KB |
Output is correct |
29 |
Correct |
1066 ms |
95424 KB |
Output is correct |
30 |
Correct |
1056 ms |
95432 KB |
Output is correct |
31 |
Correct |
970 ms |
95464 KB |
Output is correct |
32 |
Correct |
1163 ms |
95464 KB |
Output is correct |
33 |
Correct |
1237 ms |
95464 KB |
Output is correct |
34 |
Correct |
376 ms |
95464 KB |
Output is correct |
35 |
Correct |
1092 ms |
117140 KB |
Output is correct |
36 |
Correct |
1120 ms |
121704 KB |
Output is correct |
37 |
Correct |
1159 ms |
133144 KB |
Output is correct |
38 |
Correct |
1083 ms |
139600 KB |
Output is correct |
39 |
Correct |
1077 ms |
163320 KB |
Output is correct |
40 |
Correct |
1105 ms |
166908 KB |
Output is correct |
41 |
Correct |
820 ms |
169248 KB |
Output is correct |
42 |
Correct |
715 ms |
175840 KB |
Output is correct |
43 |
Correct |
996 ms |
193956 KB |
Output is correct |
44 |
Correct |
983 ms |
196388 KB |
Output is correct |
45 |
Correct |
818 ms |
217788 KB |
Output is correct |
46 |
Correct |
819 ms |
225864 KB |
Output is correct |
47 |
Correct |
942 ms |
228352 KB |
Output is correct |
48 |
Correct |
968 ms |
236984 KB |
Output is correct |
49 |
Correct |
998 ms |
245408 KB |
Output is correct |
50 |
Correct |
937 ms |
252580 KB |
Output is correct |
51 |
Correct |
1054 ms |
261104 KB |
Output is correct |
52 |
Correct |
1018 ms |
272724 KB |
Output is correct |