#include<bits/stdc++.h>
using namespace std;
int n,a,b,u_i,v_i,nxt[300005],u,it,m=0,st,md,ed,p[300005],dp[300005],mn=1e9,mx;
vector<int> v[300005],arr,g;
queue<int> q;
void dfs(int u,int fuck)
{
if(v[u].size()==1&&v[u][0]==p[u]||u==fuck)
{
dp[u]=0;
return;
}
for(int i=0;i<v[u].size();i++)
{
if(v[u][i]!=p[u])
{
p[v[u][i]]=u;
dfs(v[u][i],fuck);
}
}
for(int i=0;i<v[u].size();i++)
{
if(v[u][i]!=p[u]&&v[u][i]!=fuck)
{
g.push_back(dp[v[u][i]]);
}
}
sort(g.begin(),g.end());
for(int i=0;i<g.size();i++)
{
dp[u]=max(dp[u],g[i]+(int)g.size()-i);
}
g.clear();
}
int main()
{
scanf("%d%d%d",&n,&a,&b);
for(int i=1;i<n;i++)
{
scanf("%d%d",&u_i,&v_i);
v[u_i].push_back(v_i);
v[v_i].push_back(u_i);
}
q.push(b);
while(!q.empty())
{
u=q.front();
q.pop();
for(int i=0;i<v[u].size();i++)
{
if(nxt[v[u][i]]==0)
{
nxt[v[u][i]]=u;
q.push(v[u][i]);
}
}
}
/*for(int i=1;i<=n;i++)
{
printf("%d=%d\n",i,nxt[i]);
}*/
arr.push_back(-1);
it=a;
while(1)
{
++m;
arr.push_back(it);
if(it==b)
{
break;
}
it=nxt[it];
}
/*for(int i=1;i<=m;i++)
{
printf("%d ",arr[i]);
}
printf("\n");*/
st=1;
ed=m-1;
while(ed>=st)
{
memset(dp,0,sizeof dp);
md=(st+ed)/2;
mx=-1;
dfs(a,arr[md+1]);
mx=max(mx,dp[a]);
dfs(b,arr[md]);
mx=max(mx,dp[b]);
mn=min(mn,mx);
//printf("%d %d %d %d %d %d %d\n",st,md,ed,arr[md],arr[md+1],dp[a],dp[b]);
/*printf("%d %d %d %d %d\n",st,md,ed,dp[a],dp[b]);
for(int i=1;i<=n;i++)
{
printf("%d %d\n",i,dp[i]);
}*/
if(dp[a]>=dp[b])
{
ed=md-1;
}else
{
st=md+1;
}
}
if(a==b)
{
dfs(a,0);
printf("%d\n",dp[a]);
}else
{
printf("%d\n",mn);
}
}
Compilation message
torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:8:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
8 | if(v[u].size()==1&&v[u][0]==p[u]||u==fuck)
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
torrent.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for(int i=0;i<v[u].size();i++)
| ~^~~~~~~~~~~~
torrent.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int i=0;i<v[u].size();i++)
| ~^~~~~~~~~~~~
torrent.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i=0;i<g.size();i++)
| ~^~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i=0;i<v[u].size();i++)
| ~^~~~~~~~~~~~
torrent.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | scanf("%d%d%d",&n,&a,&b);
| ~~~~~^~~~~~~~~~~~~~~~~~~
torrent.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf("%d%d",&u_i,&v_i);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
8652 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8500 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8496 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
297 ms |
22212 KB |
Output is correct |
| 2 |
Correct |
297 ms |
23196 KB |
Output is correct |
| 3 |
Correct |
285 ms |
24116 KB |
Output is correct |
| 4 |
Correct |
294 ms |
23540 KB |
Output is correct |
| 5 |
Correct |
301 ms |
21816 KB |
Output is correct |
| 6 |
Correct |
256 ms |
22084 KB |
Output is correct |
| 7 |
Correct |
237 ms |
24164 KB |
Output is correct |
