Submission #743636

#TimeUsernameProblemLanguageResultExecution timeMemory
743636LukapTorrent (COI16_torrent)C++14
0 / 100
317 ms524288 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 3e5 + 7; int a,b,n; vector<int> susjedi[MAXN], path; int cost[MAXN]; pair<int, int> obris; vector<int> v[MAXN]; bool put (int x, int p, int y) { if (x == y) { path.push_back (x); return 1; } for (auto nx: susjedi[x]) { if (nx == p) continue; if (put (nx, x, y)) { path.push_back (x); return 1; } } } void dfs (int x, int p) { cost[x] = 0; for (auto nx: susjedi[x]) { if (nx == p) continue; if ((obris.first == x && obris.second == nx) || (obris.first == nx && obris.second == x)) continue; dfs (nx, x); v[x].push_back (cost[nx]); } sort (v[x].begin(), v[x].end ()); int cnt = 1; for (int i = v[x].size () - 1; i >= 0; i--) { cost[x] = max (cost[x], v[x][i] + cnt); cnt++; } } void clean () { for (int i = 0; i < n; i++) v[i].clear (); } int solve (int k) { obris = {path[k], path[k + 1]}; clean (); dfs (a, -1); dfs (b, -1); return max (cost[a], cost[b]); } int ts () { int lo = 0, hi = path.size() - 2; while (lo < hi) { int mid = (lo + hi) / 2; if (solve (mid) < solve (mid + 1)) hi = mid; else lo = mid + 1; } return solve (lo); } int main () { ios_base::sync_with_stdio(false); cin.tie (0); cin >> n >> a >> b; a--;b--; for (int i = 0; i < n - 1; i++) { int x, y; cin >> x >> y; x--;y--; susjedi[x].push_back (y); susjedi[y].push_back (x); } put (a, -1, b); cout << ts (); return 0; }

Compilation message (stderr)

torrent.cpp: In function 'bool put(int, int, int)':
torrent.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
   25 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...