Submission #314219

#TimeUsernameProblemLanguageResultExecution timeMemory
314219juggernautWerewolf (IOI18_werewolf)C++14
0 / 100
810 ms51696 KiB
#include"werewolf.h" #include<bits/stdc++.h> //#include"grader.cpp" #define V vector using namespace std; V<int>g[200005]; int pos[200005],logs[200005],spx[200005][18],spn[200005][18]; int gt_mx(int l,int r){ int lev=logs[r-l+1]; return max(spx[l][lev],spx[r-(1<<lev)+1][lev]); } int gt_mn(int l,int r){ int lev=logs[r-l+1]; return min(spn[l][lev],spn[r-(1<<lev)+1][lev]); } bool check(int l,int r,int nl,int nr){ if(l>r)swap(l,r); return gt_mn(l,r)>=nl&&gt_mx(l,r)<=nr; } V<int>check_validity(int n,V<int>x,V<int>y,V<int>S,V<int>E,V<int>L,V<int>R){ int root,i,j; for(i=2;i<=n;i++)logs[i]=logs[i/2]+1; V<int>res; for(i=0;i+1<n;i++){ x[i]++; y[i]++; g[x[i]].push_back(y[i]); g[y[i]].push_back(x[i]); } for(i=1;i<=n;i++)if(g[i].size()==1)root=i; spx[1][0]=root; spn[1][0]=root; pos[root]=1; int p=root; for(i=2;i<=n;i++){ if(g[root][0]!=p){ p=root; root=g[root][0]; }else{ p=root; root=g[root][1]; } spx[i][0]=root; spn[i][0]=root; pos[root]=i; } for(j=1;j<18;j++){ for(i=1;i+(1<<j)-1<=n;i++)spn[i][j]=min(spn[i][j-1],spn[i+(1<<(j-1))][j-1]); for(i=1;i+(1<<j)-1<=n;i++)spx[i][j]=max(spx[i][j-1],spx[i+(1<<(j-1))][j-1]); } for(int i=0;i<S.size();i++){ int l=pos[S[i]+1],r=pos[E[i]+1],s=L[i],e=R[i]; if(l<=r){ int mxl=n,mnr=1; while(l<mxl){ int mid=(l+mxl+1)>>1; if(check(pos[S[i]+1],mid,s,n))l=mid; else mxl=mid-1; } while(mnr<r){ int mid=(mnr+r)>>1; if(check(mid,pos[E[i]+1],1,e))r=mid; else mnr=mid+1; } res.push_back(mxl>=mnr); }else{ swap(l,r); int mxl=n,mnr=1; while(l<mxl){ int mid=(l+mxl+1)>>1; if(check(pos[S[i]+1],mid,1,e))l=mid; else mxl=mid-1; } while(mnr<r){ int mid=(mnr+r)>>1; if(check(mid,pos[E[i]+1],s,n))r=mid; else mnr=mid+1; } res.push_back(mxl>=mnr); } } return res; } /* 10 9 10 6 7 1 5 8 0 2 9 9 4 2 7 8 5 6 0 3 4 4 9 0 9 8 1 8 9 1 8 1 8 8 3 5 5 8 9 3 9 0 1 0 2 9 0 6 6 1 7 1 8 9 4 5 6 9 5 0 9 /* 1 1 1 0 1 1 0 1 0 1 */

Compilation message (stderr)

werewolf.cpp:106:1: warning: "/*" within comment [-Wcomment]
  106 | /*
      |  
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:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:31:14: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |     spx[1][0]=root;
      |     ~~~~~~~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...