#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
struct Splay
{
int p, l, r, v, sum;
bool inv;
Splay() : p(0), l(0), r(0), v(0), sum(0), inv(0) {}
} tree[400001];
vector<tuple<int,int,int>> Q[200000], B;
vector<int> ans, eidx;
bool isRoot(int c)
{
return tree[c].p==0 || tree[tree[c].p].l!=c && tree[tree[c].p].r!=c;
}
void update(int c)
{
tree[c].sum=tree[tree[c].l].sum+tree[tree[c].r].sum+tree[c].v;
}
void lazy(int c)
{
if(tree[c].inv) {
swap(tree[c].l,tree[c].r);
if(tree[c].l) tree[tree[c].l].inv^=1;
if(tree[c].r) tree[tree[c].r].inv^=1;
tree[c].inv=0;
}
}
void rotate(int c)
{
int p=tree[c].p;
if(tree[p].l==c) {
if(tree[c].r) tree[tree[c].r].p=p;
tree[p].l=tree[c].r;
tree[c].r=p;
}
else {
if(tree[c].l) tree[tree[c].l].p=p;
tree[p].r=tree[c].l;
tree[c].l=p;
}
if(!isRoot(p)) (tree[tree[p].p].l==p ? tree[tree[p].p].l:tree[tree[p].p].r)=c;
tree[c].p=tree[p].p;
tree[p].p=c;
update(p); update(c);
}
void splay(int c)
{
int cnt=0;
while(!isRoot(c)) {
int p=tree[c].p;
if(!isRoot(p)) lazy(tree[p].p);
lazy(p); lazy(c);
if(!isRoot(p)) rotate((tree[tree[p].p].l==p)==(tree[p].l==c) ? p:c);
rotate(c);
//if(++cnt==1000000) exit(0);
}
lazy(c);
}
int access(int c)
{
int ret=c;
splay(c);
tree[c].r=0;
update(c);
while(tree[c].p) {
splay(ret=tree[c].p);
tree[ret].r=c;
update(ret);
splay(c);
}
return ret;
}
int LCA(int a, int b)
{
access(a);
return access(b);
}
int findRoot(int c)
{
access(++c);
while(tree[c].l) c=tree[c].l;
splay(c);
return c;
}
void makeRoot(int c)
{
access(c);
tree[c].inv^=1;
}
void link(int a, int b) // parent[a]=b
{
makeRoot(a); access(b);
lazy(a);
tree[a].l=b;
tree[b].p=a;
update(a);
}
void cut(int a)
{
access(a);
tree[tree[a].l].p=0;
tree[a].l=0;
update(a);
}
int query(int a, int b)
{
int lca=LCA(++a,++b), ret=tree[lca].v;
access(a); splay(lca);
ret+=tree[tree[lca].r].sum;
access(b); splay(lca);
ret+=tree[tree[lca].r].sum;
return ret;
}
void add_edge(int a, int b, int c)
{
int e=eidx.back();
eidx.pop_back();
//cout<<"addedge "<<a+1<<' '<<b+1<<'\n';
tree[e]=Splay();
tree[e].v=tree[e].sum=c;
link(++a,e); link(++b,e);
B.emplace_back(e,a,b);
}
void restore(int sz)
{
int e, a, b;
while(B.size()>sz) {
tie(e,a,b)=B.back();
B.pop_back();
//cout<<"cutedge "<<a<<' '<<b<<'\n';
makeRoot(e);
cut(a); cut(b);
eidx.push_back(e);
}
}
void solve(vector<pair<int,int>> E, int s, int e)
{
int m=(s+e)>>1, bsz=B.size(), bsz2;
sort(E.begin(),E.end(),[&](pair<int,int> a, pair<int,int> b) {
int t1, t2;
t1=a.second<s || e<=a.first ? 2:!(a.first<s && e<=a.second);
t2=b.second<s || e<=b.first ? 2:!(b.first<s && e<=b.second);
return t1>t2;
});
if(s==e) {
int l, r, idx;
for(auto a: E) {
if(findRoot(a.first)!=findRoot(a.second)) {
add_edge(a.first,a.second,a.first<m && a.second>=m);
}
}
for(auto q: Q[m]) {
tie(l,r,idx)=q;
ans[idx]=query(l,r)<2;
}
restore(bsz);
return;
}
vector<pair<int,int>> NE;
for(auto a: E) {
if(a.second<s || e<=a.first) {
if(findRoot(a.first)!=findRoot(a.second)) {
add_edge(a.first,a.second,0);
NE.push_back(a);
}
}
else if(a.first<s && e<=a.second) {
if(findRoot(a.first)!=findRoot(a.second)) {
add_edge(a.first,a.second,1);
NE.push_back(a);
}
}
else {
if(findRoot(a.first)!=findRoot(a.second)) add_edge(a.first,a.second,0);
}
}
restore(bsz);
for(auto a: NE) add_edge(a.first,a.second,a.first<s && e<=a.second);
bsz2=B.size();
NE.clear();
sort(E.begin(),E.end(),[&](pair<int,int> a, pair<int,int> b) {
int t1, t2;
t1=a.second<s || e<=a.first ? 2:(a.first<s && e<=a.second);
t2=b.second<s || e<=b.first ? 2:(b.first<s && e<=b.second);
return t1>t2;
});
for(auto a: E) {
if(a.second<s || e<=a.first) {
if(findRoot(a.first)!=findRoot(a.second)) {
add_edge(a.first,a.second,0);
}
}
else if(a.first<s && e<=a.second) {
if(findRoot(a.first)!=findRoot(a.second)) {
add_edge(a.first,a.second,1);
NE.push_back(a);
}
}
else {
if(findRoot(a.first)!=findRoot(a.second)) add_edge(a.first,a.second,0);
NE.push_back(a);
}
}
restore(bsz2);
solve(NE,s,m);
solve(NE,m+1,e);
restore(bsz);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
vector<pair<int,int>> Edge;
ans.resize(S.size());
eidx.clear();
for(int i=0;i<N;i++) {
Q[i].clear();
tree[i+1]=tree[i+1+N]=Splay();
eidx.push_back(i+1+N);
}
for(int i=0;i<X.size();i++) Edge.emplace_back(min(X[i],Y[i]),max(X[i],Y[i]));
for(int i=0;i<S.size();i++) {
if(S[i]<L[i] || R[i]<E[i]) ans[i]=0;
else Q[L[i]].emplace_back(S[i],E[i],i);
}
solve(Edge,0,N-1);
return ans;
}
Compilation message
werewolf.cpp: In function 'bool isRoot(int)':
werewolf.cpp:19:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
return tree[c].p==0 || tree[tree[c].p].l!=c && tree[tree[c].p].r!=c;
~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp: In function 'void splay(int)':
werewolf.cpp:58:6: warning: unused variable 'cnt' [-Wunused-variable]
int cnt=0;
^~~
werewolf.cpp: In function 'void restore(int)':
werewolf.cpp:146:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(B.size()>sz) {
~~~~~~~~^~~
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:240:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<X.size();i++) Edge.emplace_back(min(X[i],Y[i]),max(X[i],Y[i]));
~^~~~~~~~~
werewolf.cpp:241:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<S.size();i++) {
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4086 ms |
45976 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
