#include<bits/stdc++.h>
using namespace std;
struct node {
vector<node*> l;
int a;
bool v = false;
};
struct vert{
vector<vert*> l;
int t, e, ti;
set<int>* s;
vector<int> q, Q;
};
int f(int i, int r[]){
if(r[i] == i) return i;
return r[i] = f(r[i], r);
}
void merge(int a, int b, int r[], int s[]){
a = f(a, r);
b = f(b, r);
if(a == b) return;
if(s[a] > s[b]){
r[b] = a;
s[a] += s[b];
} else {
r[a] = b;
s[b] += s[a];
}
}
int t;
vector<vert*> F;
vector<int> L, R;
void dfsH(vert* n, map<int, vert*>& cur){
cur[n->e] = n;
n->t = t++;
for(int i : n->q) F[i] = cur.lower_bound(L[i])->second;
for(vert* c : n->l) dfsH(c, cur);
n->e = t;
cur.erase(n->e);
}
void dfsW(vert* n, map<int, vert*>& cur){
cur[n->e] = n;
vert* mc = NULL;
int mx = -1;
n->t = t++;
for(vert* c : n->l){
dfsW(c, cur);
if(c->e-c->t > mx) {
mx = c->e - c->t;
mc = c;
}
}
if(mx == -1){
n->s = new set<int> ();
n->s->insert(n->ti);
} else {
n->s = mc->s;
n->s->insert(n->ti);
for(vert* c : n->l){
if(c == mc) continue;
for(int i : *c->s) n->s->insert(i);
}
}
for(int i : n->q) prev(cur.lower_bound(R[i]+1))->second->Q.push_back(i);
for(int i : n->Q){
auto p = n->s->lower_bound(F[i]->t);
if(p != n->s->end() && *p <= F[i]->e) L[i]=1;
else L[i] = 0;
}
cur.erase(n->e);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int>LT, vector<int> RT){
t = 0;
L = LT;
R = RT;
F.resize(S.size());
node g[N];
vert m[N], M[N];
int r[N], sz[N], c[N];
for(int i = 0;i < N;i++) {
g[i].a = i;
r[i] = c[i] = i;
sz[i] = 1;
}
for(int i = 0;i < X.size();i++) {
g[X[i]].l.push_back(&g[Y[i]]);
g[Y[i]].l.push_back(&g[X[i]]);
}
for(int j = 0;j < N;j++){
node* d = &g[j];
d->v = true;
for(node* x : d->l){
if(!x->v || f(x->a, r) == f(j, r)) continue;
M[j].l.push_back(&M[c[f(x->a, r)]]);
merge(x->a, j, r, sz);
c[f(j, r)] = j;
}
}
for(int i = 0;i < N;i++) {
r[i] = c[i] = i;
sz[i] = 1;
g[i].v = false;
}
for(int j = N-1;j >= 0;j--){
node* d = &g[j];
d->v = true;
for(node* x : d->l){
if(!x->v || f(x->a, r) == f(j, r)) continue;
m[j].l.push_back(&m[c[f(x->a, r)]]);
merge(x->a, j, r, sz);
c[f(j, r)] = j;
}
}
for(int i = 0;i < S.size();i++){
m[S[i]].q.push_back(i);
M[E[i]].q.push_back(i);
}
map<int, vert*> cur;
dfsH(&m[0], cur);
for(int i = 0;i < N;i++) M[i].ti = m[i].t;
dfsW(&M[N-1], cur);
return L;
}
Compilation message
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:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i = 0;i < X.size();i++) {
| ~~^~~~~~~~~~
werewolf.cpp:114:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int i = 0;i < S.size();i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
401 ms |
165224 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
