제출 #212443

#제출 시각아이디문제언어결과실행 시간메모리
212443_qVp_경주 (Race) (IOI11_race)C++14
9 / 100
3106 ms137716 KiB
#include <iostream> #include <map> #include <vector> using namespace std; const int MAXN = 2e5 + 10; const long long oo = 1e18; typedef pair < int, int > II; long long sz[MAXN], depth[MAXN], sum[MAXN]; vector < II > adj[MAXN]; vector < int > vec[MAXN]; map < long long, long long > path; int h[MAXN][2], l[MAXN]; int n, k; long long ans = oo; void dfs(int u, int p) { sz[u] = 1; for(int i = 0; i < adj[u].size(); i++) { II cur = adj[u][i]; int v = cur.first, w = cur.second; if (v == p) continue; depth[v] = depth[u] + 1; sum[v] = sum[u] + w; dfs(v, u); sz[u] += sz[v]; } } void add(int u, int k) { long long sumNow = sum[u]; long long & temp = path[sumNow]; if (k == -1) { path[sumNow] = 0; } else { long long tmp = temp; if (tmp == 0) tmp = oo; temp = min(tmp, depth[u]); } } void sack(int u, int p, int keep) { int szMax = -1, bigChild = -1; for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i].first; if (v == p) continue; if (sz[v] > szMax) { sz[v] = szMax; bigChild = v; } } for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i].first; if (v != bigChild && v != p) sack(v, u, 0); } if (bigChild != -1) { sack(bigChild, u, 1); swap(vec[u], vec[bigChild]); } vec[u].push_back(u); add(u, 1); if (path[k + sum[u]]) ans = min(ans, path[k + sum[u]] - depth[u]); for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i].first; if (v == p || v == bigChild) continue; for(int j = 0; j < vec[v].size(); j++) { int x = vec[v][j]; long long need = k + sum[u] * 2 - sum[x]; if (path[need]) ans = min(ans, path[need] + depth[x] - 2 * depth[u]); add(x, 1); vec[u].push_back(x); } } if (!keep) { for(int i = 0; i < vec[u].size(); i++) { int v = vec[u][i]; add(v, -1); } } } int solve() { dfs(0, -1); sack(0, -1, 1); return (ans == oo ? -1 : ans); } 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 u = H[i][0], v = H[i][1], w = L[i]; adj[u].push_back(II(v, w)); adj[v].push_back(II(u, w)); } return solve(); }

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

race.cpp: In function 'void dfs(int, int)':
race.cpp:21:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~
race.cpp: In function 'void sack(int, int, int)':
race.cpp:49:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~
race.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~
race.cpp:74:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~
race.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < vec[v].size(); j++) {
                  ~~^~~~~~~~~~~~~~~
race.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < vec[u].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...