제출 #221286

#제출 시각아이디문제언어결과실행 시간메모리
221286a_player경주 (Race) (IOI11_race)C++14
0 / 100
1144 ms262148 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; const int nax=2e5+5; typedef long long ll; vector<array<ll,3> > grafo[nax]; int centres[nax]; int sizes[nax]; int ans=INT_MAX; int N,K; map<ll,int> m; void incl(int n, int a, int d, ll v){ if(a!=-1){ if(m.count(K-v))ans=min(ans,m[K-v]+d); if(!m.count(v))m[v]=d; else m[v]=min(m[v],d); }else{ m.clear(); } 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(int i=0;i<grafo[n].size();i++)sizes[i]=findsize(grafo[n][i][0],-1); for(int i=0;i<grafo[i].size();i++)findc(grafo[n][i][0],-1,centres[i],sizes[i]); for(int i=0;i<grafo[n].size();i++)centroid(centres[i]); } 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],(ll)L[i],1}); grafo[H[i][1]].push_back({H[i][0],(ll)L[i],1}); } sizes[0]=findsize(0,-1); findc(0,-1,centres[0],sizes[0]); centroid(centres[0]); return ans; }

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

race.cpp: In function 'void centroid(int)':
race.cpp:47: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;
               ~^~~~~~~~~~~~~~~~
race.cpp:48:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<grafo[n].size();i++)sizes[i]=findsize(grafo[n][i][0],-1);
               ~^~~~~~~~~~~~~~~~
race.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<grafo[i].size();i++)findc(grafo[n][i][0],-1,centres[i],sizes[i]);
               ~^~~~~~~~~~~~~~~~
race.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<grafo[n].size();i++)centroid(centres[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...