| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 542921 |
2022-03-28T13:04:22 Z |
zggf |
Werewolf (IOI18_werewolf) |
C++14 |
|
1279 ms |
524288 KB |
#include "werewolf.h"
#define f first
#define s second
#include <bits/stdc++.h>
using namespace std;
bool odw[200100];
bool odw2[200100];
vector<int> graf[200100];
vector<int> maksi[200100], cent[200100], nr[200100], wart[200100];
vector<int> p1, sz1, par[20], szi[20];
vector<unordered_map<int, int>> rep[20];
int find(int x, vector<int> &parent){
if(parent[x]==-1) return x;
parent[x] = find(parent[x], parent);
return parent[x];
}
void join(int a, int b, vector<int> &parent, vector<int> &ranga, int pt=-1){
a = find(a, parent);
b = find(b, parent);
//cout<<"join: "<<a<<" "<<b<<'\n';
if(a==b) return;
if(ranga[a]>ranga[b]){
parent[b] =a;
if(pt!=-1){
maksi[a][pt] = max(maksi[a][pt], maksi[b][pt]);
for(auto it:rep[pt][b]){
if(it.s!=0) rep[pt][a][it.f] = it.s;
}
rep[pt][b].clear();
}
}else if(ranga[b]>ranga[a]){
parent[a] = b;
if(pt!=-1){
maksi[b][pt] = max(maksi[a][pt], maksi[b][pt]);
for(auto it:rep[pt][a]){
if(it.s!=0) rep[pt][b][it.f] = it.s;
}
rep[pt][a].clear();
}
}else{
parent[b] = a;
if(pt!=-1){
maksi[a][pt] = max(maksi[a][pt], maksi[b][pt]);
for(auto it:rep[pt][b]){
if(it.s!=0) rep[pt][a][it.f] = it.s;
}
rep[pt][b].clear();
}
ranga[a]++;
}
}
vector<int> G[200100];
vector<int> bylo;
vector<int> sz;
void dfs(int x, int pr=-1){
sz[x] = 1;
for(int it:G[x]){
if(it!=pr){
dfs(it, x);
sz[x]+=sz[it];
}
}
}
int centroid(int x){
for(int it:G[x]){
if(bylo[it])continue;
if(sz[x]-sz[it]<sz[it]){
swap(sz[x], sz[it]);
sz[x] = sz[it]-sz[x];
return centroid(it);
}
}
return x;
}
int globNr, globCent;
void dfs2(int x, int pr, int mini){
mini = min(mini, x);
nr[x].push_back(globNr);
cent[x].push_back(globCent);
wart[x].push_back(mini);
maksi[x].push_back(mini);
//cout<<"cent: "<<globCent<<" x: "<<x<<" wart: "<<mini<<'\n';
int pt = wart[x].size()-1;
rep[pt][x][globNr] = x+1;
for(auto it:G[x]){
if(it!=pr&&!bylo[it]){
dfs2(it, x, mini);
}
}
}
void solve(int x){
x = centroid(x);
bylo[x] = true;
globCent = x;
globNr = 0;
nr[x].push_back(-1);
cent[x].push_back(globCent);
wart[x].push_back(x);
maksi[x].push_back(x);
for(auto it:G[x]){
if(!bylo[it]){
dfs2(it, x, x);
globNr++;
}
}
for(auto it:G[x]){
if(!bylo[it]) solve(it);
}
}
void makeTree(int N){
p1.resize(N, -1);
sz.resize(N);
sz1.resize(N);
bylo.resize(N);
for(int i = 0; i < 20; i++){
szi[i].resize(N);
par[i].resize(N, -1);
rep[i].resize(N);
}
for(int i = N-1; i>=0; i--){
odw2[i] = true;
for(auto it:graf[i]){
if(odw2[it]){
if(find(it, p1)!=find(i, p1)){
join(it, i, p1, sz1);
G[it].push_back(i);
G[i].push_back(it);
}
}
}
}
dfs(0);
solve(0);
}
void add(int x){
odw[x] = true;
for(auto it:graf[x]){
if(odw[it]){
//cout<<"ADD: "<<x<<" "<<it<<'\n';
int pt = 0;
while(pt<cent[it].size()&&pt<cent[x].size()&¢[it][pt]==cent[x][pt]){
join(it, x, par[pt], szi[pt], pt);
pt++;
}
}
}
}
bool qur(int a, int b, int k){
int pt = 0;
if(!odw[b]) return false;
while(pt<cent[a].size()){
int w1 = wart[a][pt];
int vb = find(b, par[pt]);
int w2 = maksi[vb][pt];
//cout<<"A: "<<a<<" B: "<<b<<" K: "<<k<<" w1: "<<w1<<" w2: "<<w2<<'\n';
if(min(w1, w2)>=k) return true;
b = rep[pt][vb][nr[a][pt]];
b--;
//cout<<b<<'\n';
pt++;
if(b<0) return false;
}
return false;
}
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) {
int Q = S.size();
int M = X.size();
for(int i = 0; i < M; i++){
graf[X[i]].push_back(Y[i]);
graf[Y[i]].push_back(X[i]);
}
makeTree(N);
vector<pair<pair<pair<int, int>, pair<int, int>>, int>> inp;
for(int i = 0; i < Q; i++){
inp.push_back({{{R[i], L[i]}, {S[i], E[i]}}, i});
}
sort(inp.begin(), inp.end());
int poprz = 0;
vector<int> A(Q);
for(int i = 0; i < inp.size(); i++){
int l = inp[i].f.f.s;
int r = inp[i].f.f.f;
int a = inp[i].f.s.f;
int b = inp[i].f.s.s;
while(poprz<=r){
add(poprz);
poprz++;
}
//cout<<qur(a, b, l)<<'\n';
A[inp[i].s] = qur(a, b, l);
}
return A;
}
Compilation message
werewolf.cpp: In function 'void add(int)':
werewolf.cpp:155:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | while(pt<cent[it].size()&&pt<cent[x].size()&¢[it][pt]==cent[x][pt]){
| ~~^~~~~~~~~~~~~~~~
werewolf.cpp:155:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | while(pt<cent[it].size()&&pt<cent[x].size()&¢[it][pt]==cent[x][pt]){
| ~~^~~~~~~~~~~~~~~
werewolf.cpp: In function 'bool qur(int, int, int)':
werewolf.cpp:166:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | while(pt<cent[a].size()){
| ~~^~~~~~~~~~~~~~~
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:198:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<std::pair<int, int>, std::pair<int, int> >, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
198 | for(int i = 0; i < inp.size(); i++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
28628 KB |
Output is correct |
| 2 |
Correct |
14 ms |
28628 KB |
Output is correct |
| 3 |
Correct |
14 ms |
28448 KB |
Output is correct |
| 4 |
Correct |
14 ms |
28500 KB |
Output is correct |
| 5 |
Incorrect |
15 ms |
28724 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
28628 KB |
Output is correct |
| 2 |
Correct |
14 ms |
28628 KB |
Output is correct |
| 3 |
Correct |
14 ms |
28448 KB |
Output is correct |
| 4 |
Correct |
14 ms |
28500 KB |
Output is correct |
| 5 |
Incorrect |
15 ms |
28724 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1279 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
28628 KB |
Output is correct |
| 2 |
Correct |
14 ms |
28628 KB |
Output is correct |
| 3 |
Correct |
14 ms |
28448 KB |
Output is correct |
| 4 |
Correct |
14 ms |
28500 KB |
Output is correct |
| 5 |
Incorrect |
15 ms |
28724 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
