Submission #1163123

#TimeUsernameProblemLanguageResultExecution timeMemory
1163123kiethm07Torrent (COI16_torrent)C++20
0 / 100
248 ms42996 KiB
#include <bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define all(x) (x).begin(),(x).end() #define compact(x) (x).erase(all(x),(x).end()) #define pb(x) push_back(x) typedef long long ll; typedef unsigned long long ull; typedef long double ld; using namespace std; const int inf = 1e9; const ll linf = 1e18; const double pi = acos(-1); const int N = 3e5 + 5; const int LOG = 32 - __builtin_clz(N); vector<int> a[N]; int n; int r1, r2; int pa[N][LOG]; int h[N]; void dfs(int u,int p = -1){ for (int i = 1; (1 << i) <= h[i]; i++){ pa[u][i] = pa[pa[u][i-1]][i-1]; } for (int i = 0; i < a[u].size(); i++){ int v = a[u][i]; if (v == p) continue; pa[v][0] = u; h[v] = h[u] + 1; dfs(v,u); } } int cal(int u,int p,int f){ vector<int> tmp; for (int v : a[u]){ if (v == p || v == f) continue; tmp.push_back(cal(v,u,f)); } int res = 0; sort(all(tmp),greater<int>()); int k = 0; for (int i = 0; i < tmp.size(); i++){ k = max(tmp[i] + i + 1,k); } res += k; return res; } bool check(int x){ return (cal(r1,-1,x) < cal(r2,-1,pa[x][0])); } int solve(){ if (pa[r2][0] == r1) return max(cal(r1,-1,r2),cal(r2,-1,r1)); int res = r2; int k = 31 - __builtin_clz(h[r2] - 1); for (int i = k; i >= 0; i--){ if (pa[res][k] == 0) continue; int tmp = pa[res][k]; if (check(tmp)) res = tmp; } return max(cal(r1,-1,res),cal(r2,-1,pa[res][0])); } int main(){ cin.tie(0) -> sync_with_stdio(0); #define TEXT "torrent" if (fopen(TEXT".inp","r")){ freopen(TEXT".inp","r",stdin); // freopen(TEXT".out","w",stdout); } cin >> n >> r1 >> r2; for (int i = 1; i < n; i++){ int u,v; cin >> u >> v; a[u].push_back(v); a[v].push_back(u); } dfs(r1); cout << solve() << "\n"; return 0; }

Compilation message (stderr)

torrent.cpp: In function 'int main()':
torrent.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(TEXT".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...