제출 #29405

#제출 시각아이디문제언어결과실행 시간메모리
29405kavun경주 (Race) (IOI11_race)C++14
0 / 100
6 ms4988 KiB
#include "race.h" #include <bits/stdc++.h> #define pb push_back using namespace std; typedef pair<int,int> ii; typedef vector<ii> vii; bool mk[200010]; int n,k; vii adj[200010]; int sub[200010]; int ans = 1e9; int subsize(int v, int par) { int sum = 0; for(int i = 0; i < adj[v].size(); i++) if(adj[v][i].first != par && !mk[adj[v][i].first]) sum += subsize(adj[v][i].first,v); sub[v] = sum + 1; return sum + 1; } int centroid(int v, int par) { for(int i = 0; i < adj[v].size(); i++) if(adj[v][i].first != par && !mk[adj[v][i].first]) { int u = adj[v][i].first; if(sub[u] > n/2) return centroid(u,v); } return v; } void dfs(int v, int par, int d, int len, map<int,int>& m) { if(m.find(len) != m.end()) m[len] = min(m[len],d); else m[len] = d; for(int i = 0; i < adj[v].size(); i++) { int u = adj[v][i].first; int l = adj[v][i].second; if(u != par && !mk[u]) dfs(u,v,d+1,len + l, m); } } void solveForCen(int v) { map<int,int> mp; mp[0] = 0; for(int i = 0;i < adj[v].size(); i++) { if(!mk[adj[v][i].first]) { map<int,int> m; int u = adj[v][i].first; dfs(u,v,1,adj[v][i].second,m); for(map<int,int>::iterator it = m.begin(); it != m.end(); it++) { int len = it->first; if(mp.find(k - len) != mp.end()) ans = min(ans,m[len] + mp[k - len]); if(mp.find(len) != mp.end()) mp[len] = min(mp[len],m[len]); else mp[len] = m[len]; } } } } int solve(int v) { subsize(v,v); int cen = centroid(v,v); mk[cen] = true; solveForCen(cen); for(int i = 0; i < adj[cen].size(); i++) { int u = adj[cen][i].first; if(!mk[u]) solve(u); } } int best_path(int N, int K, int H[][2], int L[]) { n = N; k = K; for(int i = 0; i < N -1; i++) { int v = H[i][0],u = H[i][1],l = L[i]; adj[v].pb(ii(u,l)); adj[u].pb(ii(v,l)); } solve(0); if(ans == 1e9) return -1; else return ans; }

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

race.cpp: In function 'int subsize(int, int)':
race.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < adj[v].size(); i++)
                  ~~^~~~~~~~~~~~~~~
race.cpp: In function 'int centroid(int, int)':
race.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < adj[v].size(); i++)
                  ~~^~~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int, std::map<int, int>&)':
race.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < adj[v].size(); i++)
                  ~~^~~~~~~~~~~~~~~
race.cpp: In function 'void solveForCen(int)':
race.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i < adj[v].size(); i++)
                 ~~^~~~~~~~~~~~~~~
race.cpp: In function 'int solve(int)':
race.cpp:84:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < adj[cen].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~
race.cpp:90:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...