Submission #1087420

#TimeUsernameProblemLanguageResultExecution timeMemory
1087420smileTorrent (COI16_torrent)C++14
100 / 100
263 ms34252 KiB
#include <bits/stdc++.h> #define smile "TDL." #define mp make_pair using namespace std; typedef pair<int, int> ii; typedef long long ll; const int N = (int) 3e5 + 10; int n, m; vector<int> g[N]; int M[3]; int f[N]; int c[N]; ii banned = mp(0,0); void dfs(int u, int pre) { vector<int> tmp; f[u] = 0; c[u] = 0; for (int v: g[u]) { if (v == pre || mp(min(u, v), max(u, v)) == banned) continue; dfs(v, u); c[u]++; tmp.push_back(f[v]); } sort(tmp.begin(), tmp.end(), greater<int>()); for (int i = 0; i < tmp.size(); i++) f[u] = max(f[u], tmp[i]+i+1); } namespace SUB2 { void solve() { dfs(M[0], M[0]); cout << f[M[0]]; } } namespace SUB4 { int trace[N]; void bfs(int s, int t) { queue<int> q; q.push(s); trace[s] = -1; while (!q.empty()) { int u = q.front(); q.pop(); for (int v: g[u]) { if (!trace[v]) { trace[v] = u; q.push(v); if (v == t) return; } } } } vector<ii> e; vector<int> tmp; int calc(int u, int v) { banned = mp(min(u, v), max(u,v)); dfs(M[1], M[1]); dfs(M[0], M[0]); cerr << "cute"; int t1 = f[M[0]], t2 = f[M[1]]; if (t1 < t2) t1 += (c[M[0]] == t1); else if (t2 < t1) t2 += (c[M[1]] == t2); else if (c[M[0]] == t1 && c[M[1]] == t2) t1++; return max(t1, t2); } int ans = INT_MAX; bool ok() { dfs(M[1], M[1]); dfs(M[0], M[0]); int t1 = f[M[0]], t2 = f[M[1]]; if (t1 < t2) t1 += (c[M[0]] == t1); else if (t2 < t1) t2 += (c[M[1]] == t2); else if (c[M[0]] == t1 && c[M[1]] == t2) t1++; ans = min(ans, max(t1, t2)); return t1 < t2; } void T() { int tl = calc(tmp[0], tmp[1]), tr = calc(tmp[tmp.size()-2], tmp[tmp.size()-1]); int l = 1, r = tmp.size()-2; /* for (int i = 17; i >= 0; i--) { if (l + (1 << i) > r) continue; int j = l + (1 << i); int u = tmp[j], v = tmp[j-1]; if (calc(u, v) == tl) l += (1 << i); } for (int i = 17; i >= 0; i--) { if (r - (1 << i) < l) continue; int j = r - (1 << i); int u = tmp[j], v = tmp[j+1]; if (calc(u, v) == tr) r -= (1 << i); } for (int i = 17; i >= 0; i--) { if (l + (1 << i) > r) continue; int j = l + (1 << i); int s = tmp[j-1], u = tmp[j], v = tmp[j+1]; if (calc(s, u) > calc(u, v)) l += (1 << i); } for (int i = 17; i >= 0; i--) { if (l + (1 << i) > r) continue; int j = r - (1 << i); int s = tmp[j-1], u = tmp[j], v = tmp[j+1]; if (calc(s, u) < calc(u, v)) r -= (1 << i); } for (int i = l-1; i <= r; i++) ans = min(ans, calc(tmp[i], tmp[i+1])); */ while (l <= r) { int m = (l + r) >> 1; banned = mp(min(tmp[m], tmp[m-1]), max(tmp[m], tmp[m-1])); if (ok()) l = m + 1; else r = m - 1; } // cout << l << ' ' << r << '\n'; cout << ans; } void solve() { int ans = INT_MAX; bfs(M[0], M[1]); int v = M[1]; while (v != -1) { tmp.push_back(v); v = trace[v]; } reverse(tmp.begin(), tmp.end()); T(); } } int main() { // freopen(smile"inp", "r", stdin); // freopen(smile"out", "w", stdout); // time_t bg = clock(); cin.tie(0) -> sync_with_stdio(0); cin >> n >> M[0] >> M[1]; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } // cin >> m; // for (int i = 0; i < m; i++) // cin >> M[i]; // if (m == 1) // SUB2::solve(); // else SUB4::solve(); // cerr << '\n' << setprecision(5) << fixed << (double) (clock() - bg) / CLOCKS_PER_SEC; return 0; }

Compilation message (stderr)

torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < tmp.size(); i++)
      |                     ~~^~~~~~~~~~~~
torrent.cpp: In function 'void SUB4::T()':
torrent.cpp:100:13: warning: unused variable 'tl' [-Wunused-variable]
  100 |         int tl = calc(tmp[0], tmp[1]),
      |             ^~
torrent.cpp:101:13: warning: unused variable 'tr' [-Wunused-variable]
  101 |             tr = calc(tmp[tmp.size()-2], tmp[tmp.size()-1]);
      |             ^~
torrent.cpp: In function 'void SUB4::solve()':
torrent.cpp:149:13: warning: unused variable 'ans' [-Wunused-variable]
  149 |         int ans = INT_MAX;
      |             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...