| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 116230 |
2019-06-11T11:16:37 Z |
zubec |
Werewolf (IOI18_werewolf) |
C++14 |
|
1234 ms |
100068 KB |
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200100;
vector <vector <int> > g, g1, g2;
int dsu[2][N], fenw[N], n;
int tin[2][N], tout[2][N], tiktak, up[2][20][N], pos[N];
int dsu_get(int pr, int v){
if (v == dsu[pr][v])
return v;
return dsu[pr][v] = dsu_get(pr, dsu[pr][v]);
}
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;
}
void dfs(vector <vector <int> > &g, int cur, int v, int p){
tin[cur][v] = ++tiktak;
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]];
}
for (int i = 0; i < g[v].size(); i++){
int to = g[v][i];
dfs(g, cur, to, v);
}
tout[cur][v] = tiktak;
}
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;
g.resize(n);
g1.resize(n);
g2.resize(n);
for (int i = 0; i <= n; i++){
dsu[0][i] = dsu[1][i] = i;
fenw[i] = 0;
}
int Q = S.size();
std::vector<int> A(Q);
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 (to < i)
continue;
int a = dsu_get(0, i);
int b = dsu_get(0, to);
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(1, i);
int b = dsu_get(1, to);
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(1, 0), dsu_get(1, 0));
vector <pair<int, pair<int, int> > > zapr;
for (int i = 0; i < Q; 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 tim = zapr[i].first, id = zapr[i].second.first, v = zapr[i].second.second;
while(ptr < tim){
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 < n; i++){
A[i] = (A[i] > 0);
}
return A;
}
Compilation message
werewolf.cpp: In function 'void dfs(std::vector<std::vector<int> >&, int, int, int)':
werewolf.cpp:39: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:60:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < X.size(); i++){
~~^~~~~~~~~~
werewolf.cpp:66:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < g[i].size(); j++){
~~^~~~~~~~~~~~~
werewolf.cpp:79:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < g[i].size(); j++){
~~^~~~~~~~~~~~~
werewolf.cpp:114:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < zapr.size(); i++){
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
640 KB |
Output is correct |
| 2 |
Correct |
2 ms |
640 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
640 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
640 KB |
Output is correct |
| 2 |
Correct |
2 ms |
640 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
640 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1234 ms |
83636 KB |
Output is correct |
| 2 |
Correct |
959 ms |
94068 KB |
Output is correct |
| 3 |
Correct |
910 ms |
90368 KB |
Output is correct |
| 4 |
Correct |
976 ms |
88632 KB |
Output is correct |
| 5 |
Correct |
991 ms |
88528 KB |
Output is correct |
| 6 |
Correct |
1071 ms |
88424 KB |
Output is correct |
| 7 |
Correct |
1127 ms |
88280 KB |
Output is correct |
| 8 |
Correct |
773 ms |
93840 KB |
Output is correct |
| 9 |
Correct |
587 ms |
90052 KB |
Output is correct |
| 10 |
Correct |
528 ms |
88456 KB |
Output is correct |
| 11 |
Correct |
584 ms |
88356 KB |
Output is correct |
| 12 |
Correct |
593 ms |
88168 KB |
Output is correct |
| 13 |
Correct |
926 ms |
100068 KB |
Output is correct |
| 14 |
Correct |
925 ms |
99936 KB |
Output is correct |
| 15 |
Correct |
886 ms |
100028 KB |
Output is correct |
| 16 |
Correct |
891 ms |
99908 KB |
Output is correct |
| 17 |
Correct |
1125 ms |
87896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
640 KB |
Output is correct |
| 2 |
Correct |
2 ms |
640 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
640 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
