제출 #446656

#제출 시각아이디문제언어결과실행 시간메모리
446656Giselus경주 (Race) (IOI11_race)C++14
0 / 100
3 ms4940 KiB
#include<cstdio> #include<algorithm> #include<vector> #include<map> #define S 200007 using namespace std; vector < pair < int , int > > V[S]; int roz[S]; bool deleted[S]; void DFS(int x, int r){ roz[x] = 1; for(int i = 0 ; i < V[x].size();i++){ if(V[x][i].first != r && !deleted[V[x][i].first]){ DFS(V[x][i].first,x); roz[x] += roz[V[x][i].first]; } } } int Find(int x){ for(int i = 0 ; i < V[x].size();i++){ if(!deleted[V[x][i].first]){ if(roz[V[x][i].first] > roz[x]/2){ roz[x] -= roz[V[x][i].first]; roz[V[x][i].first] += roz[x]; return Find(V[x][i].first); } } } return x; } long long dp[S]; int l = 0; int L[S]; int R[S]; int ID[S]; int poz[S]; void DFS2(int x, int r){ L[x] = ++l; ID[l] = x; for(int i = 0 ; i < V[x].size();i++){ int v = V[x][i].first; int c = V[x][i].second; if(v != r && !deleted[v]){ poz[v] = poz[x] + 1; dp[v] = dp[x] + c; DFS2(v,x); } } R[x] = l; } long long k; int odp = 1e9; map < long long , int > mapa; void decomposition(int x){ DFS(x,x); int centroid = Find(x); DFS2(centroid,centroid); deleted[centroid] = 1; for(int i = 0 ; i < V[centroid].size();i++){ int v = V[centroid][i].first; if(!deleted[v]){ for(int j = L[v]; j <= R[v];j++){ int v2 = ID[j]; if(dp[v2] == k) odp = min(odp,poz[v2]); if(mapa[k-dp[v2]]){ odp = min(odp, poz[v2] + mapa[k-dp[v2]]); } } for(int j = L[v]; j <= R[v];j++){ int v2 = ID[j]; if(!mapa[dp[v2]]){ mapa[dp[v2]] = poz[v2]; }else{ mapa[dp[v2]] = min(mapa[dp[v2]],poz[v2]); } } } } l = 0; mapa.clear(); for(int i = 0 ; i < V[centroid].size();i++){ int v = V[centroid][i].first; if(!deleted[v]) decomposition(v); } } int best_path(int n, int _k, int H[][2], int L[]){ k = _k; for(int i = 0 ; i < n-1;i++){ V[H[i][0]+1].push_back({H[i][1]+1,L[i]}); V[H[i][1]+1].push_back({H[i][0]+1,L[i]}); } decomposition(1); return odp; } /* int main(void){ int A[3][2] = {{0,1}, {1,2}, {1,3}}; int B[3] = {1,2,4}; printf("%d",best_path(4,3,A,B)); return 0; } */

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

race.cpp: In function 'void DFS(int, int)':
race.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i = 0 ; i < V[x].size();i++){
      |                     ~~^~~~~~~~~~~~~
race.cpp: In function 'int Find(int)':
race.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 0 ; i < V[x].size();i++){
      |                     ~~^~~~~~~~~~~~~
race.cpp: In function 'void DFS2(int, int)':
race.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 0 ; i < V[x].size();i++){
      |                     ~~^~~~~~~~~~~~~
race.cpp: In function 'void decomposition(int)':
race.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i = 0 ; i < V[centroid].size();i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~
race.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i = 0 ; i < V[centroid].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...