| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 82793 |
2018-11-01T17:41:56 Z |
zubec |
Werewolf (IOI18_werewolf) |
C++14 |
|
1130 ms |
95572 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(), 0);
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, e}});
zapr.push_back({tout[0][s], {i, 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)] -= (get(tout[1][v])-get(tin[1][v]-1));
} else {
A[abs(id)] += (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 |
3 ms |
632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
772 KB |
Output is correct |
| 3 |
Correct |
2 ms |
772 KB |
Output is correct |
| 4 |
Correct |
2 ms |
772 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
920 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
772 KB |
Output is correct |
| 3 |
Correct |
2 ms |
772 KB |
Output is correct |
| 4 |
Correct |
2 ms |
772 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
920 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1130 ms |
82944 KB |
Output is correct |
| 2 |
Correct |
999 ms |
88588 KB |
Output is correct |
| 3 |
Correct |
998 ms |
88588 KB |
Output is correct |
| 4 |
Correct |
1031 ms |
88588 KB |
Output is correct |
| 5 |
Correct |
991 ms |
88588 KB |
Output is correct |
| 6 |
Correct |
1068 ms |
88588 KB |
Output is correct |
| 7 |
Correct |
1082 ms |
88588 KB |
Output is correct |
| 8 |
Correct |
880 ms |
89304 KB |
Output is correct |
| 9 |
Correct |
613 ms |
89304 KB |
Output is correct |
| 10 |
Correct |
561 ms |
89304 KB |
Output is correct |
| 11 |
Correct |
637 ms |
89304 KB |
Output is correct |
| 12 |
Correct |
622 ms |
89304 KB |
Output is correct |
| 13 |
Correct |
1028 ms |
95572 KB |
Output is correct |
| 14 |
Incorrect |
963 ms |
95572 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
772 KB |
Output is correct |
| 3 |
Correct |
2 ms |
772 KB |
Output is correct |
| 4 |
Correct |
2 ms |
772 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
920 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
