Submission #380199

#TimeUsernameProblemLanguageResultExecution timeMemory
380199sadWerewolf (IOI18_werewolf)C++14
0 / 100
4035 ms39988 KiB
#include "werewolf.h" #include<bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back using namespace std; int n; const int N=200090; int idx[N],vis[N],a[N],treemn[N*4],treemx[N*4]; vector<int>v[N]; void go (int x,int y) { idx[x]=y; a[y]=x; vis[x]=1; for(auto it:v[x]) { if(vis[it]) continue; go(it,y+1); } } int get1 (int ind,int st,int end,int l,int r,int x) { for(int i=l; i<=r; i++) { if(a[i]>x) return i-1; } return r; if(r<l) return 0; if(l>end||r<st) return (end-st+1); int m=(st+end )/2; int re=0; if(l<=st&&end<=r) { if(st==end&&a[st]<=x) return 1; else if(st==end) return 0; if(treemx[ind]<=x) return (end-st+1); if(treemx[ind*2+1]<=x) { re=get1(ind*2+2,m+1,end,l,r,x); re+=m+1-st; return re; } re=get1(ind*2+1,st,m,l,r,x); return re; } re=get1(ind*2+1,st,m,l,r,x); if(re==m+1-st) { re+=get1(ind*2+2,m+1,end,l,r,x); return re; } return re; } int get (int ind,int st,int end,int l,int r,int x) { for(int i=l; i<=r; i++) { if(a[i]<x) return i-1; } return r; if(r<l) return 0; if(l>end||r<st) return (end-st+1); int m=(st+end )/2; int re=0; if(l<=st&&end<=r) { if(st==end&&a[st]>=x) return 1; else if(st==end) return 0; if(treemn[ind]>=x) return (end-st+1); if(treemn[ind*2+1]>=x) { re=get(ind*2+2,m+1,end,l,r,x); re+=m+1-st; return re; } re=get(ind*2+1,st,m,l,r,x); return re; } re=get(ind*2+1,st,m,l,r,x); if(re==m+1-st) { re+=get(ind*2+2,m+1,end,l,r,x); return re; } return re; } void build(int ind,int st,int end) { if(st==end) { treemx[ind]=a[st]; treemn[ind]=a[st]; return; } int m=(st+end)/2; build(ind*2+1,st,m); build(ind*2+2,m+1,end); treemn[ind]=min(treemn[ind*2+1],treemn[ind*2+2]); treemx[ind]=max(treemx[ind*2+1],treemx[ind*2+2]); } vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E, vector<int> L, vector<int> R) { memset(a,0,sizeof a); memset(treemn,0,sizeof treemn); memset(treemx,0,sizeof treemx); memset(idx,0,sizeof idx); for(int i=0; i<n+3; i++) a[i]=n+1; for(int i=0; i<n+3; i++) v[i].clear(); n=N; int m=X.size(); for(int i=0; i<m; i++) { v[X[i]].pb(Y[i]); v[Y[i]].pb(X[i]); } int st=0; for(int i=0; i<n; i++) { if(v[i].size()==1) { st=i; break; } } vector<int>ans; ans.clear(); go(st,1); build(0,1,n); int q=S.size(); for(int i=0; i<q; i++) { int s=S[i],e=E[i],l=L[i],r=R[i]; if(s<l||e>r) { ans.pb(0); continue; } if(idx[s]>idx[e]) { int x=get1(0,1,n,idx[e],n,r); if(x>=idx[s]) { ans.pb(1); continue; } if(a[x]<l) { ans.pb(0); continue; } x=get(0,1,n,x,n,l); if(x>=idx[s]) ans.pb(1); else ans.pb(0); continue; } int x=get(0,1,n,idx[s],n,l); if(x>=idx[e]) { ans.pb(1); continue; } if(a[x]>r) { ans.pb(0); continue; } x=get1(0,1,n,x,n,r); if(x>=idx[e]) ans.pb(1); else ans.pb(0); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...