Submission #139800

#TimeUsernameProblemLanguageResultExecution timeMemory
139800almogwaldWerewolf (IOI18_werewolf)C++14
0 / 100
716 ms92844 KiB
#include <utility> #include <algorithm> #include <math.h> #include <vector> #include <set> #include <iostream> //#include "job.h" #include "werewolf.h" #define fori(i,n) for(int i=0;i<n;i++) #define forn(i,n) for(int i=1;i<n;i++) #define forib(i,n) for(int i=n-1;i>=0;i--) #define fornb(i,n) for(int i=n-1;i>0;i--) #define maxl 10000000000 #define con continue; typedef long long lol; using namespace std; typedef vector<int> veci; typedef pair<lol,lol> point; lol sum=0; #define k 20 veci check_validity(int n, veci X, veci Y,veci S, veci E,veci L,veci R) { vector<vector<int>> cons(n); int Q = S.size(); veci A(Q); fori(i,X.size()){ cons[X[i]].push_back(Y[i]); cons[Y[i]].push_back(X[i]); } int cur=0; fori(i,n){ if(cons[i].size()==1){ cur=i; break; } } int p=cur; veci ord; veci place(n); place[cur]=0; ord.push_back(cur); bool ok=true; while(ok){ ok=false; fori(i,cons[cur].size()){ if(cons[cur][i]!=p){ ok=true; place[cons[cur][i]]=ord.size(); ord.push_back(cons[cur][i]); p=cur; cur=cons[cur][i]; break; } } } veci had; vector<veci> l1(k,veci(n)); vector<veci> l2(k,veci(n)); fori(i,n){ while(!had.empty() && ord[had.back()]>ord[i]){ had.pop_back(); } l1[0][i]=i; if(had.size()){ l1[0][i]=had.back(); } had.push_back(i); forn(j,k){ l1[j][i]=l1[j-1][l1[j-1][i]]; } } had.resize(0); forib(i,n){ while(!had.empty() && ord[had.back()]>ord[i]){ had.pop_back(); } l2[0][i]=i; if(had.size()){ l2[0][i]=had.back(); } had.push_back(i); forn(j,k){ l2[j][i]=l2[j-1][l2[j-1][i]]; } } had.resize(0); vector<veci> r1(k,veci(n)); vector<veci> r2(k,veci(n)); fori(i,n){ while(!had.empty() && ord[had.back()]<ord[i]){ had.pop_back(); } r1[0][i]=i; if(had.size()){ r1[0][i]=had.back(); } had.push_back(i); forn(j,k){ r1[j][i]=r1[j-1][r1[j-1][i]]; } } had.resize(0); forib(i,n){ while(!had.empty() && ord[had.back()]<ord[i]){ had.pop_back(); } r2[0][i]=i; if(had.size()){ r2[0][i]=had.back(); } had.push_back(i); forn(j,k){ r2[j][i]=r2[j-1][r2[j-1][i]]; } } fori(p,Q) { if(S[p]<L[p]|| E[p]>R[p]){ con } int poss=place[S[p]]; int pose=place[E[p]]; if(poss<pose){ int m=19; if(ord[l2[m][poss]]>=L[p]){ A[p]=1; con } while(m>=0){ if(ord[l2[m][poss]]>=L[p]){ poss=l2[m][poss]; con } m--; } m=19; if(ord[r1[m][pose]]<=R[p]){ A[p]=1; con } while(m>=0){ if(ord[r1[m][pose]]<=R[p]){ pose=r1[m][pose]; con } m--; } if(pose<=poss){ A[p]=1; } }else{ int m=19; if(ord[l1[m][poss]]>=L[p]){ A[p]=1; con } while(m>=0){ if(ord[l1[m][poss]]>=L[p]){ poss=l1[m][poss]; con } m--; } m=19; if(ord[r2[m][pose]]<=R[p]){ A[p]=1; con } while(m>=0){ if(ord[r2[m][pose]]<=R[p]){ pose=r2[m][pose]; con } m--; } if(poss<=pose){ A[p]=1; } } } return A; }

Compilation message (stderr)

werewolf.cpp: In function 'veci check_validity(int, veci, veci, veci, veci, veci, veci)':
werewolf.cpp:9:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(i,n) for(int i=0;i<n;i++)
werewolf.cpp:26:7:
  fori(i,X.size()){
       ~~~~~~~~~~                
werewolf.cpp:26:2: note: in expansion of macro 'fori'
  fori(i,X.size()){
  ^~~~
werewolf.cpp:9:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(i,n) for(int i=0;i<n;i++)
werewolf.cpp:45:8:
   fori(i,cons[cur].size()){
        ~~~~~~~~~~~~~~~~~~       
werewolf.cpp:45:3: note: in expansion of macro 'fori'
   fori(i,cons[cur].size()){
   ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...