제출 #221296

#제출 시각아이디문제언어결과실행 시간메모리
221296a_player경주 (Race) (IOI11_race)C++14
0 / 100
3064 ms9352 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; const int nax=2e5+5; const int vax=1e6+5; typedef long long ll; vector<array<int,3> > grafo[nax]; int ans=INT_MAX; int N,K; int ss,cc; int m[vax]; void incl(int n, int a, int d, int v){ if(K<v)return; if(a!=-1){ if(m[K-v]!=-1)ans=min(ans,m[K-v]+d); if(m[v]==-1)m[v]=d; else m[v]=min(m[v],d); }else{ fill(m,m+vax,-1); } for(auto x:grafo[n]){ if(!x[2]||x[0]==a)continue; incl(x[0],n,d+1,v+x[1]); } } int findc(int n, int a, int& c, int num){ int s=0; for(auto x:grafo[n]){ if(!x[2]||x[0]==a)continue; s+=findc(x[0],n,c,num); } if(abs(s-num/2)<=1)c=n; return s+1; } int findsize(int n, int a){ int s=0; for(auto x:grafo[n]){ if(!x[2]||x[0]==a)continue; s+=findsize(x[0],n); } return s+1; } void centroid(int n){ incl(n,-1,0,0); for(int i=0;i<grafo[n].size();i++)grafo[n][i][2]=0; for(auto x:grafo[n]){ ss=findsize(x[0],-1); findc(x[0],-1,cc,ss); centroid(cc); } } int best_path(int N, int K, int H[][2], int L[]){ ::N=N,::K=K; for(int i=0;i<N-1;i++){ grafo[H[i][0]].push_back({H[i][1],L[i],1}); grafo[H[i][1]].push_back({H[i][0],L[i],1}); } ss=findsize(0,-1); findc(0,-1,cc,ss); centroid(cc); return ans; }

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

race.cpp: In function 'void centroid(int)':
race.cpp:48:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<grafo[n].size();i++)grafo[n][i][2]=0;
               ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...