#include <bits/stdc++.h>
#define MAXN 200007
using namespace std;
const int bucket_sz=5;
int n,m,a,b,bucket[MAXN],q,l,r;
struct event{
int id;
int val;
int tim;
};
struct qr{
int s,e;
int l,r;
int id;
inline friend bool operator < (qr fr,qr sc){
if(bucket[fr.l]!=bucket[sc.l])return bucket[fr.l]<bucket[sc.l];
else return fr.r<sc.r;
}
};
vector<int> v[MAXN];
stack<event> sl,sr;
qr qs[MAXN];
int ldsu[MAXN],rdsu[MAXN],lsz[MAXN],rsz[MAXN];
int timl,timr;
vector<int> ans;
int rootL(int x){
if(ldsu[x]==x)return ldsu[x];
return rootL(ldsu[x]);
}
int rootR(int x){
if(rdsu[x]==x)return rdsu[x];
return rootR(rdsu[x]);
}
void connectL(int x,int y){
timl++;
int rootx=rootL(x);
int rooty=rootL(y);
if(rootx==rooty)return;
if(lsz[rootx]<lsz[rooty])swap(rootx,rooty);
sl.push({rooty,ldsu[rooty],timl});
sl.push({-rootx,lsz[rootx],timl});
ldsu[rooty]=rootx; lsz[rootx]+=lsz[rooty];
}
void connectR(int x,int y){
timr++;
int rootx=rootR(x);
int rooty=rootR(y);
if(rootx==rooty)return;
if(rsz[rootx]<rsz[rooty])swap(rootx,rooty);
sr.push({rooty,rdsu[rooty],timr});
sr.push({-rootx,rsz[rootx],timr});
rdsu[rooty]=rootx; rsz[rootx]+=rsz[rooty];
}
void undoL(){
while(!sl.empty() and sl.top().tim==timl){
if(sl.top().id<0)lsz[-sl.top().id]=sl.top().val;
else ldsu[sl.top().id]=sl.top().val;
sl.pop();
}
timl--;
}
void undoR(){
while(!sr.empty() and sr.top().tim==timr){
if(sr.top().id<0)rsz[-sr.top().id]=sr.top().val;
else rdsu[sr.top().id]=sr.top().val;
sr.pop();
}
timr--;
}
void pushfront(int x){
for(int i=0;i<v[x].size();i++){
if(v[x][i]>x)connectL(x,v[x][i]);
}
}
void popfront(int x){
for(int i=0;i<v[x].size();i++){
if(v[x][i]>x)undoL();
}
}
void pushback(int x){
for(int i=0;i<v[x].size();i++){
if(v[x][i]<x)connectR(x,v[x][i]);
}
}
void popback(int x){
for(int i=0;i<v[x].size();i++){
if(v[x][i]<x)undoR();
}
}
int check(int s,int e){
for(int i=0;i<n;i++){
if(rootL(i)==rootL(s) and rootR(i)==rootR(e))return 1;
}
return 0;
}
vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R){
n=N; m=int(X.size()); q=int(S.size());
ans.resize(q);
for(int i=0;i<n;i++){
ldsu[i]=rdsu[i]=i;
lsz[i]=rsz[i]=1;
}
for(int i=1;i<=m;i++){
a=X[i-1]; b=Y[i-1];
v[a].push_back(b);
v[b].push_back(a);
}
for(int i=0;i<=n;i++){
bucket[i]=i/bucket_sz;
}
for(int i=0;i<q;i++){
qs[i].s=S[i]; qs[i].e=E[i]; qs[i].l=L[i]; qs[i].r=R[i];
qs[i].id=i;
}
sort(qs,qs+q);
l=n; r=-1;
for(int i=0;i<q;i++){
while(l>qs[i].l){
l--; pushfront(l);
}
while(l<qs[i].l){
popfront(l); l++;
}
while(r<qs[i].r){
r++; pushback(r);
}
while(r>qs[i].r){
popback(r); r--;
}
ans[qs[i].id]=check(qs[i].s,qs[i].e);
}
return ans;
}
Compilation message
werewolf.cpp: In function 'void pushfront(int)':
werewolf.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
werewolf.cpp: In function 'void popfront(int)':
werewolf.cpp:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
werewolf.cpp: In function 'void pushback(int)':
werewolf.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
werewolf.cpp: In function 'void popback(int)':
werewolf.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 10 |
Correct |
79 ms |
5644 KB |
Output is correct |
| 11 |
Correct |
90 ms |
5632 KB |
Output is correct |
| 12 |
Correct |
99 ms |
5636 KB |
Output is correct |
| 13 |
Correct |
42 ms |
5640 KB |
Output is correct |
| 14 |
Correct |
50 ms |
5668 KB |
Output is correct |
| 15 |
Correct |
119 ms |
5748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4038 ms |
47436 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 10 |
Correct |
79 ms |
5644 KB |
Output is correct |
| 11 |
Correct |
90 ms |
5632 KB |
Output is correct |
| 12 |
Correct |
99 ms |
5636 KB |
Output is correct |
| 13 |
Correct |
42 ms |
5640 KB |
Output is correct |
| 14 |
Correct |
50 ms |
5668 KB |
Output is correct |
| 15 |
Correct |
119 ms |
5748 KB |
Output is correct |
| 16 |
Execution timed out |
4038 ms |
47436 KB |
Time limit exceeded |
| 17 |
Halted |
0 ms |
0 KB |
- |
