Submission #100376

#TimeUsernameProblemLanguageResultExecution timeMemory
100376MvCWerewolf (IOI18_werewolf)C++11
49 / 100
790 ms49944 KiB
#pragma GCC optimize("O3") #include<bits/stdc++.h> #define rc(x) return cout<<x<<endl,0 #define pb push_back #define in insert #define er erase #define fd find #define fr first #define sc second typedef long long ll; typedef long double ld; const ll INF=0x3f3f3f3f3f3f3f3f; const ll llinf=(1LL<<62); const int inf=(1<<30); const int nmax=2e5+1; const int mod=1e9+7; using namespace std; int n,i,j,t,m,q,l[nmax],r[nmax],s[nmax],e[nmax],id[nmax],bit[nmax],x,y,st,dr,rs,mid,lf[nmax],rg[nmax],v1[3050],v2[3050]; vector<int>g[nmax],vl[nmax],vr[nmax]; void upd(int i) { for(;i<=n;i+=i&(-i))bit[i]++; } int qry(int i) { if(!i)return 0; int sm=0; for(;i>=1;i-=i&(-i))sm+=bit[i]; return sm; } void dfs(int x,int p) { id[x]=id[p]+1; for(int i=0;i<g[x].size();i++) { if(g[x][i]==p)continue; dfs(g[x][i],x); } } void dfs1(int x,int cmp) { v1[x]=1; for(int i=0;i<g[x].size();i++)if(g[x][i]>=cmp && !v1[g[x][i]])dfs1(g[x][i],cmp); } void dfs2(int x,int cmp) { v2[x]=1; for(int i=0;i<g[x].size();i++)if(g[x][i]<=cmp && !v2[g[x][i]])dfs2(g[x][i],cmp); } 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(); vector<int>ans; for(i=0;i<m;i++) { x=X[i],y=Y[i]; x++,y++; g[x].pb(y); g[y].pb(x); } if(n<=3000) { for(i=1;i<=q;i++) { s[i]=S[i-1],e[i]=E[i-1],l[i]=L[i-1],r[i]=R[i-1]; s[i]++,e[i]++,l[i]++,r[i]++; dfs1(s[i],l[i]); dfs2(e[i],r[i]); for(j=1;j<=n;j++)if(v1[j] && v2[j])break; if(j<=n)ans.pb(1); else ans.pb(0); memset(v1,0,sizeof(v1)); memset(v2,0,sizeof(v2)); } return ans; } for(i=1;i<=n;i++) { if(g[i].size()==1) { x=i; break; } } dfs(x,x); for(i=1;i<=q;i++) { s[i]=S[i-1],e[i]=E[i-1],l[i]=L[i-1],r[i]=R[i-1]; s[i]++,e[i]++,l[i]++,r[i]++; s[i]=id[s[i]],e[i]=id[e[i]]; vl[l[i]].pb(i); vr[r[i]].pb(i); } for(i=n;i>=1;i--) { upd(id[i]); for(j=0;j<vl[i].size();j++) { t=vl[i][j]; if(s[t]<e[t]) { st=s[t],dr=e[t],rs=-1; x=qry(s[t]-1); while(st<=dr) { mid=(st+dr)/2; if(qry(mid)-x==mid-s[t]+1)rs=mid,st=mid+1; else dr=mid-1; } } else { st=e[t],dr=s[t],rs=-1; x=qry(s[t]); while(st<=dr) { mid=(st+dr)/2; if(x-qry(mid-1)==s[t]-mid+1)rs=mid,dr=mid-1; else st=mid+1; } } lf[t]=rs; } } memset(bit,0,sizeof(bit)); for(i=1;i<=n;i++) { upd(id[i]); for(j=0;j<vr[i].size();j++) { t=vr[i][j]; if(s[t]<e[t]) { st=s[t],dr=e[t],rs=-1; x=qry(e[t]); while(st<=dr) { mid=(st+dr)/2; if(x-qry(mid-1)==e[t]-mid+1)rs=mid,dr=mid-1; else st=mid+1; } } else { st=e[t],dr=s[t],rs=-1; x=qry(e[t]-1); while(st<=dr) { mid=(st+dr)/2; if(qry(mid)-x==mid-e[t]+1)rs=mid,st=mid+1; else dr=mid-1; } } rg[t]=rs; } } for(i=1;i<=q;i++) { if(s[i]<e[i]) { if(lf[i]==-1 || rg[i]==-1 || lf[i]<rg[i])ans.pb(0); else ans.pb(1); } else { if(lf[i]==-1 || rg[i]==-1 || lf[i]>rg[i])ans.pb(0); else ans.pb(1); } } return ans; } /*int main() { //freopen("sol.in","r",stdin); //freopen("sol.out","w",stdout); ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0); cin>>n>>m>>q; while(m--) { cin>>x>>y; x++,y++; g[x].pb(y); g[y].pb(x); } for(i=1;i<=n;i++) { if(g[i].size()==1) { x=i; break; } } dfs(x,x); for(i=1;i<=q;i++) { cin>>s[i]>>e[i]>>l[i]>>r[i]; s[i]++,e[i]++,l[i]++,r[i]++; s[i]=id[s[i]],e[i]=id[e[i]]; vl[l[i]].pb(i); vr[r[i]].pb(i); } for(i=n;i>=1;i--) { upd(id[i]); for(j=0;j<vl[i].size();j++) { t=vl[i][j]; if(s[t]<e[t]) { st=s[t],dr=e[t],rs=-1; x=qry(s[t]-1); while(st<=dr) { mid=(st+dr)/2; if(qry(mid)-x==mid-s[t]+1)rs=mid,st=mid+1; else dr=mid-1; } } else { st=e[t],dr=s[t],rs=-1; x=qry(s[t]); while(st<=dr) { mid=(st+dr)/2; if(x-qry(mid-1)==s[t]-mid+1)rs=mid,dr=mid-1; else st=mid+1; } } lf[t]=rs; } } memset(bit,0,sizeof(bit)); for(i=1;i<=n;i++) { upd(id[i]); for(j=0;j<vr[i].size();j++) { t=vr[i][j]; if(s[t]<e[t]) { st=s[t],dr=e[t],rs=-1; x=qry(e[t]); while(st<=dr) { mid=(st+dr)/2; if(x-qry(mid-1)==e[t]-mid+1)rs=mid,dr=mid-1; else st=mid+1; } } else { st=e[t],dr=s[t],rs=-1; x=qry(e[t]-1); while(st<=dr) { mid=(st+dr)/2; if(qry(mid)-x==mid-e[t]+1)rs=mid,st=mid+1; else dr=mid-1; } } rg[t]=rs; } } for(i=1;i<=q;i++) { if(s[i]<e[i]) { if(lf[i]==-1 || rg[i]==-1 || lf[i]<rg[i])cout<<0<<" "; else cout<<1<<" "; } else { if(lf[i]==-1 || rg[i]==-1 || lf[i]>rg[i])cout<<0<<" "; else cout<<1<<" "; } cout<<lf[i]<<" "<<rg[i]<<endl; } cout<<endl; return 0; } /* 8 7 1 0 2 2 4 4 1 1 6 6 5 5 3 3 7 4 7 3 7 */

Compilation message (stderr)

werewolf.cpp:282:1: warning: "/*" within comment [-Wcomment]
 /*
  
werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[x].size();i++)
              ~^~~~~~~~~~~~
werewolf.cpp: In function 'void dfs1(int, int)':
werewolf.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[x].size();i++)if(g[x][i]>=cmp && !v1[g[x][i]])dfs1(g[x][i],cmp);
              ~^~~~~~~~~~~~
werewolf.cpp: In function 'void dfs2(int, int)':
werewolf.cpp:48:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[x].size();i++)if(g[x][i]<=cmp && !v2[g[x][i]])dfs2(g[x][i],cmp);
              ~^~~~~~~~~~~~
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:97:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<vl[i].size();j++)
           ~^~~~~~~~~~~~~
werewolf.cpp:129:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<vr[i].size();j++)
           ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...