Submission #846592

#TimeUsernameProblemLanguageResultExecution timeMemory
846592danglayloi1Torrent (COI16_torrent)C++17
69 / 100
359 ms35784 KiB
#include <bits/stdc++.h> #define fi first #define se second #define inf 0x3f3f3f3f using namespace std; using ll = long long; const int nx=3e5+5; int n, a, b, p[nx], ans, d, c, g, pos, dp[nx]; bool vis[nx]; vector<int> adj[nx], tmp[nx]; map<pair<int, int>, int> mp; vector<pair<int, int>> path; void find(int u) { if(u==b) return; vis[u]=1; for(int v:adj[u]) { if(!vis[v]) { p[v]=u; find(v); } } } void dfs(int u, int s, int t) { vis[u]=1; for(int v:adj[u]) { if(u==s && v==t) continue; if(u==t && v==s) continue; if(!vis[v]) { dfs(v, s, t); tmp[u].emplace_back(dp[v]); } } int cur=0; sort(tmp[u].begin(), tmp[u].end(), greater<int>()); for(int i = 0; i < tmp[u].size(); i++) cur=max(cur, tmp[u][i]+i+1); dp[u]=cur; } int cnt(int s, int t) { memset(dp, 0x3f, sizeof(dp)); memset(vis, 0, sizeof(vis)); for(int i = 1; i <= n; i++) tmp[i].clear(); dfs(a, s, t); dfs(b, s, t); return max(dp[a], dp[b]); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>a>>b; for(int i = 1; i < n; i++) { int u, v; cin>>u>>v; adj[u].emplace_back(v); adj[v].emplace_back(u); } find(a); int s=b; while(s!=a) { path.emplace_back(s, p[s]); s=p[s]; } d=0; c=path.size()-1; ans=inf; while(d<=c) { g=(d+c)/2; if(cnt(path[g].fi, path[g].se)<ans) { ans=cnt(path[g].fi, path[g].se); d=g+1; pos=g; } else c=g-1; } if(pos) { pos--; ans=min(ans, cnt(path[pos].fi, path[pos].se)); } if(ans==inf) ans=0; cout<<ans; }

Compilation message (stderr)

torrent.cpp: In function 'void dfs(int, int, int)':
torrent.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 0; i < tmp[u].size(); i++)
      |                    ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...