Submission #1113813

#TimeUsernameProblemLanguageResultExecution timeMemory
1113813_callmelucianTorrent (COI16_torrent)C++14
100 / 100
320 ms46072 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pl; typedef pair<int,int> pii; typedef tuple<int,int,int> tpl; #define all(a) a.begin(), a.end() #define filter(a) a.erase(unique(all(a)), a.end()) const int mn = 3e5 + 5; int up[mn][19]; vector<int> adj[mn]; void preDfs (int u, int p) { up[u][0] = p; for (int i = 1; i < 19; i++) up[u][i] = up[up[u][i - 1]][i - 1]; for (int v : adj[u]) if (v != p) preDfs(v, u); } int solve (int u, int p, int block) { vector<int> line; for (int v : adj[u]) if (v != p && v != block) line.push_back(solve(v, u, block)); sort(all(line), greater<int>()); int ans = 0; for (int i = 0; i < line.size(); i++) ans = max(ans, line[i] + i + 1); return ans; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, u, v; cin >> n >> u >> v; for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } preDfs(u, u); int ans = max(solve(u, u, v), solve(v, v, up[v][0])), optNode = v; for (int i = 18; i >= 0; i--) { if (up[optNode][i] == u) continue; int tmp = up[optNode][i], calcU = solve(u, u, tmp), calcV = solve(v, v, up[tmp][0]); if (calcU >= calcV) optNode = tmp, ans = max(calcU, calcV); } if (up[optNode][0] != u) ans = min(ans, max(solve(u, u, up[optNode][0]), solve(v, v, up[optNode][1]))); cout << ans; return 0; }

Compilation message (stderr)

torrent.cpp: In function 'int solve(int, int, int)':
torrent.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < line.size(); i++) ans = max(ans, line[i] + i + 1);
      |                     ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...