Submission #114451

#TimeUsernameProblemLanguageResultExecution timeMemory
114451mosesmayerRace (IOI11_race)C++17
100 / 100
1573 ms49804 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> #include "race.h" #define fi first #define se second using namespace std; //using namespace __gnu_pbds; typedef vector<int> vi; typedef pair<int,int> pii; const int MXN = 1e6; const int mxsz = 2e5 + 3; int n, k; vector<pii> adj[mxsz]; int sz[mxsz], dep[mxsz], bc[mxsz], in[mxsz], out[mxsz], flat[mxsz]; long long dist[mxsz]; unordered_map<long long, int> sack; void getsz(int u, int prv = -1){ static int tme = 0; in[u] = ++tme; flat[tme] = u; sz[u] = 1; for (int i = 0, nx, w; i < adj[u].size(); i++){ nx = adj[u][i].fi; w = adj[u][i].se; if (nx == prv) continue; dep[nx] = dep[u] + 1; dist[nx] = dist[u] + w; getsz(nx, u); sz[u] += sz[nx]; if (bc[u] == -1 || sz[nx] > sz[bc[u]]) bc[u] = nx; } out[u] = tme; } int ans = 0x3f3f3f3f; void dfs(int u, int prv, bool keep){ for (int i = 0, nx; i < adj[u].size(); i++){ nx = adj[u][i].fi; if (nx == prv || nx == bc[u]) continue; dfs(nx, u, 0); } if (bc[u] != -1) dfs(bc[u], u, 1); sack[dist[u]] = u; if (bc[u] != -1){ long long w = k + dist[u]; if (sack.find(w) != sack.end()){ ans = min(ans, dep[sack[w]] - dep[u]); } } for (int i = 0, nx, w; i < adj[u].size(); i++){ nx = adj[u][i].fi; if (nx == prv || nx == bc[u]) continue; for (int j = in[nx]; j <= out[nx]; j++){ int x = flat[j]; long long w = dist[x] - dist[u] - dist[u]; w = 1LL * k - w; if (sack.find(w) != sack.end()){ int y = sack[w]; ans = min(ans, dep[x] + dep[y] - 2 * dep[u]); } } for (int j = in[nx]; j <= out[nx]; j++){ int x = flat[j]; long long w = dist[x]; if (sack.find(w) == sack.end() || dep[x] < dep[sack[w]]) sack[w] = x; } } if (!keep){ sack.clear(); } } int best_path(int N, int K, int H[][2], int L[]) { n = N; k = K; for (int i = 0; i < n-1; i++){ adj[H[i][0]].emplace_back(H[i][1], L[i]); adj[H[i][1]].emplace_back(H[i][0], L[i]); } memset(bc, -1, sizeof(bc)); getsz(0); dfs(0, -1, 1); if (ans == 0x3f3f3f3f) return -1; return ans; }

Compilation message (stderr)

race.cpp: In function 'void getsz(int, int)':
race.cpp:24:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0, nx, w; i < adj[u].size(); i++){
                         ~~^~~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, bool)':
race.cpp:39:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0, nx; i < adj[u].size(); i++){
                      ~~^~~~~~~~~~~~~~~
race.cpp:52:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0, nx, w; i < adj[u].size(); i++){
                         ~~^~~~~~~~~~~~~~~
race.cpp:52:22: warning: unused variable 'w' [-Wunused-variable]
  for (int i = 0, nx, w; i < adj[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...