# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
86843 | rzbt | Torrent (COI16_torrent) | C++14 | 210 ms | 49416 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 300005
typedef long long ll;
using namespace std;
int n,a,b;
vector<int> niz[MAXN];
int los[MAXN],otac[MAXN];
vector<int> zbirovi[MAXN];
vector<int> kriticni;
bool dfsinit(int t,int o){
otac[t]=o;
if(t==b){
los[b]=o;
return true;
}
for(auto x:niz[t]){
if(x==o)continue;
if(dfsinit(x,t)){
los[t]=x;
if(t!=a)kriticni.pb(t);
return true;
}
}
return false;
}
int dfs1(int t,int o){
for(auto x:niz[t]){
if(x==o || los[t]==x)continue;
zbirovi[t].pb(dfs1(x,t));
}
sort(all(zbirovi[t]),greater<int>());
for(int i=0;i<zbirovi[t].size();i++)zbirovi[t][i]+=i+1;
int mx=0;
for(auto x:zbirovi[t])mx=max(x,mx);
//printf(" %d %d %d\n",t,o,mx+1);
return mx;
}
int main()
{
scanf("%d %d %d", &n, &a, &b);
for(int i=1;i<n;i++){
int t1,t2;
scanf("%d %d", &t1, &t2);
niz[t1].pb(t2);
niz[t2].pb(t1);
}
dfsinit(a,0);
int res=max(dfs1(a,0),dfs1(b,otac[b]))+1;
//printf(" lepetije lepetije\n");
for(int i=0;i<kriticni.size();i++)res=max(res,min(1+i,(int)kriticni.size()-i)+dfs1(kriticni[i],otac[kriticni[i]]));
if(kriticni.empty())res--;
printf("%d",res);
return 0;
}
/*
Typical effects of MDMA include anxiety relief, disinhibition, enhanced empathy and sociability, relaxation, and euphoria. MDMA is classified as an entactogen due to how it facilitates feelings of closeness with oneself and others. It is commonly associated with dance parties, raves, and electronic dance music
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |