Submission #544195

#TimeUsernameProblemLanguageResultExecution timeMemory
544195levladiatorTorrent (COI16_torrent)C++14
0 / 100
2 ms1364 KiB
#include <bits/stdc++.h> #define pb push_back #define pf push_front #define ll long long #define ull unsigned long long #define pii pair<int,int> #define pll pair<ll,ll> #define EPSILON 0.000001 #define CH (*s-'a') using namespace std; const ll NMAX = 3e3 + 5, INF = 1e18, MOD = 1e9 + 7, MMAX = 1e2 + 5, inf = 1e9; ifstream fin("date.in"); ofstream fout("date.out"); int N,A,B; int cost[NMAX],par[NMAX]; vector<int> chain; set<int> adj[NMAX]; void path(int node,int prev) { par[node]=prev; if(node==B) { int x=B; while(x!=A) { chain.pb(x); x=par[x]; } chain.pb(A); return; } for(auto son : adj[node]) { if(son==prev) continue; path(son,node); } } int dfs(int node,int prev) { for(auto son : adj[node]) { if(son==prev) continue; dfs(son,node); } multiset<int> aux; for(auto son : adj[node]) { if(son==prev) continue; aux.insert(cost[son]); } int sons=aux.size(); for(auto x : aux) { cost[node]=max(cost[node],x+sons); sons--; } } int main() { cin.tie ( 0 )->sync_with_stdio ( 0 ); cin.tie ( NULL ); cout.tie ( NULL ); cin>>N>>A>>B; for(int i=1;i<N;i++) { int a,b; cin>>a>>b; adj[a].insert(b); adj[b].insert(a); } path(A,0); reverse(chain.begin(),chain.end()); int lo=0,hi=chain.size()-2; int ans=1e9; while(lo<=hi) { for(int i=1;i<=N;i++) { cost[i]=0; } int mid=(lo+hi)/2; int c=chain[mid],d=chain[mid+1]; adj[c].erase(d); adj[d].erase(c); dfs(A,0); dfs(B,0); if(cost[A]<=cost[B]) { lo=mid+1; } else hi=mid-1; ans=min(ans,max(cost[A],cost[B])); adj[c].insert(d); adj[d].insert(c); } cout<<ans; return 0; }

Compilation message (stderr)

torrent.cpp: In function 'int dfs(int, int)':
torrent.cpp:67:1: warning: no return statement in function returning non-void [-Wreturn-type]
   67 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...