#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
const int N=4e5+99;
int n,t,Time,par[N],pos[N],A[N],B[N],mark[N],st[2][N],ft[2][N],L[2][N],R[2][N];
pair<int,int> seg[N<<1];
vector<int> ans,ad[N],dl[N],adj[N],g[2][N];
vector<pair<int,int>> vec[2][N];
int getpar(int u){
if(par[u]<0) return u;
return par[u]=getpar(par[u]);
}
void merge(int u,int v,int s){
u=getpar(u),v=getpar(v);
if(u==v) return ;
if(s^(u<v)) swap(u,v);
par[u]+=par[v];
par[v]=u;
}
void dfs(int u,int s){
st[s][u]=Time++;
for(auto v : g[s][u]){
dfs(v,s);
}
ft[s][u]=Time;
}
void upd(int x,pair<int,int> val){
seg[x+t]=val;
for(x+=t;x>1;x>>=1){
seg[x>>1]=max(seg[x],seg[x^1]);
}
}
pair<int,int> get(int l,int r){
pair<int,int> ans=mp(-1,0);
for(l+=t,r+=t;l<r;l>>=1,r>>=1){
if(l&1){
maxm(ans,seg[l++]);
}
if(r&1){
maxm(ans,seg[--r]);
}
}
return ans;
}
vector<int> check_validity(int _n,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> C,vector<int> D){
f(i,0,N<<1) seg[i].F=-1;
n=_n,t=S.size();
f(i,0,X.size()) adj[X[i]].pb(Y[i]),adj[Y[i]].pb(X[i]);
fill(par,par+N,-1);
f(i,0,t){
ans.pb(0);
swap(S[i],E[i]);
L[0][i]=R[0][i]=L[1][i]=R[1][i]=n;
vec[0][D[i]].pb({S[i],i});
vec[1][C[i]].pb({E[i],i});
}
f(u,0,n){
for(auto v : adj[u]){
v=getpar(v);
if(v<u){
//cout<<u<<" -> "<<v<<endl;
merge(u,v,0);
g[0][u].pb(v);
}
}
for(auto p : vec[0][u]){
A[p.S]=getpar(p.F);
}
}
fill(par,par+N,-1);
f_(u,n-1,0){
for(auto v : adj[u]){
v=getpar(v);
if(v>u){
merge(u,v,1);
g[1][u].pb(v);
}
}
for(auto p : vec[1][u]){
B[p.S]=getpar(p.F);
}
}
dfs(n-1,0);
Time=0,dfs(0,1);
f(i,0,t){
L[0][i]=st[0][A[i]];
R[0][i]=ft[0][A[i]];
L[1][i]=st[1][B[i]];
R[1][i]=ft[1][B[i]];
}
f(i,0,n) A[st[0][i]]=i,B[st[1][i]]=i;
/*dbga(A,0,n);
dbga(B,0,n);
f(i,0,t){
cout<<L[0][i]<<" "<<R[0][i]<<endl;
cout<<L[1][i]<<" "<<R[1][i]<<endl;
cout<<endl;
}*/
vector<int> p(t);
iota(all(p),0);
sort(all(p),[&](int u,int v){ return L[1][u]<L[1][v]; });
f(i,0,t) pos[p[i]]=i;
f(i,0,t){
ad[L[0][i]].pb(i);
dl[R[0][i]].pb(i);
}
f(i,0,n){
for(auto id : ad[i]) upd(pos[id],mp(R[1][id],id));
for(auto id : dl[i]) upd(pos[id],mp(-1,id));
int x=st[1][A[i]];
//cout<<A[i]<<" -> "<<st[1][A[i]]<<endl;
int l=-1,r=n,mid;
while(l+1<r){
int mid=(l+r)>>1;
if(L[1][p[mid]]<=x) l=mid;
else r=mid;
}
/*
for(pair<int,int> P=get(0,r);P.F>x;P=get(0,r)){
//erorp(P);
ans[P.S]=1;
upd(pos[P.S],mp(-1,P.S));
}*/
f(j,0,r){
if(get(j,j+1).F>x){
ans[get(j,j+1).S]=1;
upd(pos[get(j,j+1).S],mp(-1,-1));
}
}
}
return ans;
}
/*
6 6 3
3 0
3 1
3 4
1 2
2 5
5 1
4 2 2 2
5 4 3 4
4 2 1 2
*/
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:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
70 | f(i,0,X.size()) adj[X[i]].pb(Y[i]),adj[Y[i]].pb(X[i]);
| ~~~~~~~~~~~~
werewolf.cpp:70:3: note: in expansion of macro 'f'
70 | f(i,0,X.size()) adj[X[i]].pb(Y[i]),adj[Y[i]].pb(X[i]);
| ^
werewolf.cpp:134:18: warning: unused variable 'mid' [-Wunused-variable]
134 | int l=-1,r=n,mid;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
73924 KB |
Output is correct |
| 2 |
Correct |
33 ms |
73980 KB |
Output is correct |
| 3 |
Incorrect |
35 ms |
73956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
73924 KB |
Output is correct |
| 2 |
Correct |
33 ms |
73980 KB |
Output is correct |
| 3 |
Incorrect |
35 ms |
73956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4048 ms |
121984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
73924 KB |
Output is correct |
| 2 |
Correct |
33 ms |
73980 KB |
Output is correct |
| 3 |
Incorrect |
35 ms |
73956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
