#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
const int N=200007,M=400007,Q=200007;
vector<int> G[N];
vector<int> G1[N];
vector<int> DG[N+M];
int dsu[N];
vector<pair<int,int>>poc[N];
vector<pair<int,int>>kon[N];
int q[Q][2];
pair<int,int>seg[Q][2];
int Find(int v)
{
if(v==dsu[v]) return v;
return dsu[v]=Find(dsu[v]);
}
int it;
void Union(int u,int v)
{
u=Find(u),v=Find(v);
it++;
dsu[it]=it;
dsu[u]=it;
dsu[v]=it;
DG[it].pb(u);
if(v!=u) DG[it].pb(v);
}
int pre[N],post[N],c;
int a1[N],a2[N];
void dfs(int v,bool b)
{
if(sz(DG[v])==0)
{
pre[v]=++c;
if(b) a2[c]=v;
else a1[c]=v;
post[v]=c;
}
else
{
pre[v]=inf;
post[v]=0;
}
for(auto u:DG[v])
{
dfs(u,b);
pre[v]=min(pre[v],pre[u]);
post[v]=max(post[v],post[u]);
}
}
int tree[4*N],pot=1;
vector<pair<pair<int,int>,pair<int,int>>>vec[N];
int que(int v,int a,int b,int l,int r)
{
if(a<=l&&b>=r) return tree[v];
if(l>b||r<a) return 0;
return max(que(2*v,a,b,l,(l+r)/2),que(2*v+1,a,b,(l+r)/2+1,r));
}
void ins(int u,int v)
{
int y=u+pot-1;
tree[y]=v;
while(y>1)
{
y/=2;
tree[y]=max(tree[2*y],tree[2*y+1]);
}
}
vector<int> check_validity(int n,vector<int> X,vector<int> Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R)
{
for(int i=0;i<sz(X);i++)
{
X[i]++;
Y[i]++;
if(X[i]>Y[i])
{
G1[X[i]].pb(Y[i]);
G[Y[i]].pb(X[i]);
}
else
{
G[X[i]].pb(Y[i]);
G1[Y[i]].pb(X[i]);
}
}
for(int i=0;i<sz(S);i++)
{
S[i]++;
E[i]++;
L[i]++;
R[i]++;
poc[L[i]].pb({S[i],i});
kon[R[i]].pb({E[i],i});
}
it=n;
for(int i=1;i<=n;i++) dsu[i]=i;
for(int i=n;i>0;i--)
{
for(auto u:G[i]) Union(i,u);
for(auto x:poc[i]) q[x.nd][0]=Find(x.st);
}
for(int i=1;i<=it;i++) if(Find(i)==i) dfs(i,0);
for(int i=0;i<sz(S);i++) seg[i][0]={pre[q[i][0]],post[q[i][0]]};
for(int i=1;i<=it;i++) DG[i].clear();
it=n,c=0;
for(int i=1;i<=n;i++) dsu[i]=i;
for(int i=1;i<=n;i++)
{
for(auto u:G1[i]) Union(i,u);
for(auto x:kon[i]) q[x.nd][1]=Find(x.st);
}
for(int i=1;i<=it;i++) if(Find(i)==i) dfs(i,1);
for(int i=0;i<sz(S);i++) seg[i][1]={pre[q[i][1]],post[q[i][1]]};
while(pot<n) pot*=2;
for(int i=0;i<sz(S);i++)
{
// cout<<seg[i][0].st<<" "<<seg[i][0].nd<<" "<<seg[i][1].st<<" "<<seg[i][1].nd<<endl;
vec[seg[i][0].nd].pb({{seg[i][0].st,i},{seg[i][1].st,seg[i][1].nd}});
}
vector<int>ans(sz(S));
for(int i=1;i<=n;i++)
{
ins(pre[a1[i]],i);
for(auto x:vec[i])
{
//cout<<x.st.nd<<" "<<que(1,x.nd.st,x.nd.nd,1,pot)<<endl;
if(que(1,x.nd.st,x.nd.nd,1,pot)>=x.st.st&&S[x.st.nd]>=L[x.st.nd]&&E[x.st.nd]<=R[x.st.nd]) ans[x.st.nd]=1;
}
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int nn,mm,qq;
cin>>nn>>mm>>qq;
vector<int> xx(mm),yy(mm);
for(int i=0;i<mm;i++) cin>>xx[i];
for(int i=0;i<mm;i++) cin>>yy[i];
vector<int> ss(qq),ee(qq),LL(qq),rr(qq);
for(int i=0;i<qq;i++) cin>>ss[i];
for(int i=0;i<qq;i++) cin>>ee[i];
for(int i=0;i<qq;i++) cin>>LL[i];
for(int i=0;i<qq;i++) cin>>rr[i];
vector<int> veccc=check_validity(nn,xx,yy,ss,ee,LL,rr);
for(auto x:veccc) cout<<x<<' ';
return 0;
}
Compilation message
/tmp/ccozU1rB.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccWCZrW4.o:werewolf.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
