제출 #115006

#제출 시각아이디문제언어결과실행 시간메모리
115006dsjong늑대인간 (IOI18_werewolf)C++14
0 / 100
482 ms524288 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; vector<int>adj[200005]; int a[200005],pos[200005]; int last=0,cnt=0; void dfs(int i,int p,int t){ pos[i]=cnt; if(t==2) a[cnt++]=i; last=i; for(int j:adj[i]){ if(j==p) continue; dfs(j,i,t); } } int st1[200005][10],st2[200005][10]; void build(){ for(int i=0;i<cnt;i++){ st1[i][0]=st2[i][0]=a[i]; } for(int j=1;j<19;j++){ for(int i=0;i<=cnt-(1<<j);i++){ st1[i][j]=min(st1[i][j-1],st1[i+(1<<(j-1))][j-1]); st2[i][j]=max(st2[i][j-1],st2[i+(1<<(j-1))][j-1]); } } } int query(int l,int r,int t){ if(l>r) swap(l,r); int k=log2(r-l+1); //if(t==1) cout<<"QUERY MIN "<<l<<" "<<r<<" "<<min(st1[l][k],st1[r-(1<<k)+1][k])<<endl; //else cout<<"QUERY MAX "<<l<<" "<<r<<" "<<max(st2[l][k],st2[r-(1<<k)+1][k])<<endl; if(t==1) return min(st1[l][k],st1[r-(1<<k)+1][k]); else return max(st2[l][k],st2[r-(1<<k)+1][k]); } int check(int s,int e,int m,int l,int r){ int q1=query(s,m,1),q2=query(m,e,2); if(q1>=l&&q2<=r) return 0; //GOOD else if(q1>=l) return 1; //MOVE RIGHT else if(q2<=r) return 2; //MOVE LEFT else return 3; //BAD } vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) { for(int i=0;i<X.size();i++){ adj[X[i]].push_back(Y[i]); adj[Y[i]].push_back(X[i]); } dfs(0,-1,1); dfs(last,-1,2); vector<int>ans; /*for(int i=0;i<N;i++){ cout<<a[i]<<" "; } cout<<endl;*/ build(); for(int i=0;i<S.size();i++){ int s=pos[S[i]],e=pos[E[i]],l=L[i],r=R[i]; //cout<<s<<" "<<e<<" "<<l<<" "<<r<<": "; int ll=s,rr=e; if(s<e){ while(ll<rr){ int mm=(ll+rr)/2; //cout<<mm<<" "; int ch=check(s,e,mm,l,r); if(ch==0){ ans.push_back(1); goto hell; } else if(ch==3){ ans.push_back(0); goto hell; } else if(ch==1) ll=mm+1; else rr=mm-1; if(ll>rr){ ans.push_back(0); goto hell; } } } else{ while(ll>rr){ int mm=(ll+rr)/2; //cout<<mm<<" "; int ch=check(s,e,mm,l,r); if(ch==0){ ans.push_back(1); goto hell; } else if(ch==3){ ans.push_back(0); goto hell; } else if(ch==1) ll=mm-1; else rr=mm+1; if(ll<rr){ ans.push_back(0); goto hell; } } } //cout<<ll<<" "; if(check(s,e,ll,l,r)==0){ ans.push_back(1); } else ans.push_back(0); hell:; //cout<<endl; } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

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:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~
werewolf.cpp:58:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<S.size();i++){
              ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...