Submission #639531

#TimeUsernameProblemLanguageResultExecution timeMemory
639531FEDIKUSTorrent (COI16_torrent)C++17
100 / 100
379 ms27144 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") #define mp make_pair #define pb push_back #define pf push_front #define popb pop_back #define popf pop_front #define xx first #define yy second #define srt(a) sort(a.begin(),a.end()); #define srtg(a,int) sort(a.begin(),a.end(),greater<int>()) #define lb(a,x) lower_bound(a.begin(),a.end(),x) #define up(a,x) upper_bound(a.begin(),a.end(),x) #define fnd(a,x) find(a.begin(),a.end(),x) #define vstart auto startt=chrono::system_clock::now() #define vend auto endd=chrono::system_clock::now() #define vvreme chrono::duration<double> vremee=endd-startt #define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef string str; const int maxn=3e5+10; vector<int> g[maxn]; stack<int> tren; vector<int> put; int duzine[maxn]; int a,b; bool dfs1(int cvor,int prosli){ tren.push(cvor); if(cvor==b) return true; for(int i:g[cvor]){ if(i==prosli) continue; if(dfs1(i,cvor)) return true; } tren.pop(); return false; } int dfs2(int cvor,int prosli,int k1,int k2){ int cena=0; vector<int> val; for(int i:g[cvor]){ if((cvor==k1 && i==k2) || (cvor==k2 && i==k1)) continue; if(i==prosli) continue; val.pb(dfs2(i,cvor,k1,k2)); } sort(val.begin(),val.end()); int k=val.size(); for(int i:val){ cena=max(cena,i+(k--)); } return cena; } int dfs3(int cvor,int prosli,int k1,int k2){ int ret=1; for(int i:g[cvor]){ if(i==prosli || i==k1 || i==k2) continue; ret+=dfs3(i,cvor,k1,k2); } return ret; } void solve(){ int n; cin>>n; cin>>a>>b; for(int i=1;i<n;i++){ int c,d; cin>>c>>d; g[c].pb(d); g[d].pb(c); } dfs1(a,-1); while(!tren.empty()){ put.pb(tren.top()); tren.pop(); } int res=INT_MAX; int l=0; int r=put.size()-2; while(l<=r){ int mid=l+(r-l)/2; int sta2=dfs2(a,-1,put[mid],put[mid+1]); int sta1=dfs2(b,-1,put[mid],put[mid+1]); res=min(res,max(sta1,sta2)); if(sta1==sta2){ break; } if(sta1>sta2){ r=mid-1; }else if(sta1<sta2) l=mid+1; } cout<<res; } int main(){ ios; int t=1; //cin>>t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...