제출 #138908

#제출 시각아이디문제언어결과실행 시간메모리
138908Hassoony늑대인간 (IOI18_werewolf)C++17
0 / 100
1775 ms524292 KiB
#include <bits/stdc++.h> #include "werewolf.h" //#include "grader.cpp" using namespace std; const int MX=2e5+9; int n,in[MX],timer,org[MX],seg[MX*5],seg1[MX*5],ind[MX*5]; vector<int>v[MX]; void dfs(int x,int p){ in[x]=++timer; org[timer]=x; for(auto pp:v[x]){ if(pp==p)continue; dfs(pp,x); } } void build(int node,int l,int r){ if(l == r){ seg[node] = org[l]; ind[node] = l; return; } int mid=(l+r)/2; build(node*2,l,mid); build(node*2+1,mid+1,r); seg[node]=min(seg[node*2],seg[node*2+1]); if(seg[node*2] < seg[node*2+1]) ind[node] = ind[node*2]; else ind[node] = ind[node*2+1]; } pair<int,int> q(int node,int l,int r,int s,int e,bool ok){ if(l > e || r < s)return {MX,-1}; if(l >= s && r <= e)return {seg[node],ind[node]}; int mid=(l+r)/2; pair<int,int> p1=q(node*2,l,mid,s,e,ok); pair<int,int> p2=q(node*2+1,mid+1,r,s,e,ok); if(ok == 0){ if(p1.first < p2.first) return p1; else return p2; } else{ if(p1.first <= p2.first) return p1; else return p2; } } void build1(int node,int l,int r){ if(l == r){ seg1[node] = org[l]; return; } int mid=(l+r)/2; build1(node*2,l,mid); build1(node*2+1,mid+1,r); seg1[node]=max(seg1[node*2],seg1[node*2+1]); } int q1(int node,int l,int r,int s,int e){ if(l > e || r < s)return -1; if(l >= s && r <= e)return seg1[node]; int mid=(l+r)/2; return max(q1(node*2,l,mid,s,e),q1(node*2+1,mid+1,r,s,e)); } 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; for(int i=0;i<X.size();i++){ v[X[i]].push_back(Y[i]); v[Y[i]].push_back(X[i]); } int root=0; for(int i=0;i<n;i++){ if(v[i].size() == 1)root = i; } dfs(root,-1); build(1,1,n); build1(1,1,n); vector<int>res; for(int i=0;i<S.size();i++){ int s=S[i],e=E[i]; if(in[s] > in[e]){ int r=in[s],l=in[e]; int ans=-1; while(l<=r){ int mid=(l+r)/2; if(q(1,1,n,mid,in[s],1).first >= L[i]){ ans=q(1,1,n,mid,in[s],1).second; l=mid+1; } else r=mid-1; } if(ans == -1){ res.push_back(0); continue; } if(q1(1,1,n,in[e],ans) > R[i]){ res.push_back(0); } else res.push_back(1); continue; } int l=in[s],r=in[e]; int ans=-1; while(l<=r){ int mid=(l+r)/2; if(q(1,1,n,in[s],mid,0).first >= L[i]){ ans=q(1,1,n,in[s],mid,0).second; l=mid+1; } else r=mid-1; } if(ans == -1){ res.push_back(0); continue; } if(q1(1,1,n,ans,in[e]) > R[i]){ res.push_back(0); } else res.push_back(1); } return res; } /* 6 5 1 3 1 1 0 0 4 4 2 2 5 */

컴파일 시 표준 에러 (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:70:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<X.size();i++){
                 ~^~~~~~~~~
werewolf.cpp:82:18: 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...