oj.uz

Submission #763889

# Submission time Handle Problem Language Result Execution time Memory
763889 2023-06-23T02:23:32 Z jamielim Torrent (COI16_torrent) C++14
100 / 100
 753 ms 54376 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
typedef pair<int,int> ii;
typedef long long ll;
typedef unsigned long long ull;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const ll MOD=1000000007;

int n,a,b;
set<int> adj[300005];
int dist[300005];
int dp[300005];
vector<ii> edges;

void dfs(int x,int p){
	vector<int> v;
	for(int i:adj[x]){
		if(i==p)continue;
		dfs(i,x);
		v.pb(dp[i]);
	}
	sort(ALL(v));
	for(int i=0;i<SZ(v);i++){
		dp[x]=max(dp[x],v[i]+SZ(v)-i);
	}
}

// remove/add the edge that is x nodes above b in the tree rooted at a
void cut_edge(int x){
	memset(dp,0,sizeof(dp));
	int p=edges[x].fi,q=edges[x].se;
	adj[p].erase(q);
	adj[q].erase(p);
}
void add_edge(int x){
	int p=edges[x].fi,q=edges[x].se;
	adj[p].insert(q);
	adj[q].insert(p);
}

int main(){
	scanf("%d%d%d",&n,&a,&b);
	int x,y;
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		adj[x].insert(y);
		adj[y].insert(x);
	}
	for(int i=1;i<=n;i++)dist[i]=INF;
	dist[a]=0;
	queue<int> q;q.push(a);
	while(!q.empty()){
		int cur=q.front();q.pop();
		for(int i:adj[cur]){
			if(dist[i]>dist[cur]+1){
				dist[i]=dist[cur]+1;
				q.push(i);
			}
		}
	}
	int retrace=b;
	while(retrace!=a){
		for(int i:adj[retrace]){
			if(dist[i]==dist[retrace]-1){
				edges.pb(i,retrace);
				retrace=i;
				break;
			}
		}
	}
	
	int l=0,r=dist[b]-1;
	while(l<r){
		int m=(l+r)/2;
		cut_edge(m);
		dfs(a,0);dfs(b,0);
		add_edge(m);
		if(dp[a]>dp[b])l=m+1;
		else r=m;
	}
	int ans=n-2;
	if(l>0){
		int m=l-1;
		cut_edge(m);
		dfs(a,0);dfs(b,0);
		add_edge(m);
		ans=min(ans,max(dp[a],dp[b]));
	}
	cut_edge(l);
	dfs(a,0);dfs(b,0);
	add_edge(l);
	ans=min(ans,max(dp[a],dp[b]));
	printf("%d",ans);
}

Compilation message

torrent.cpp: In function 'int main()':
torrent.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%d%d%d",&n,&a,&b);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
torrent.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15572 KB Output is correct
2 Correct 9 ms 15572 KB Output is correct
3 Correct 9 ms 15572 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 753 ms 50608 KB Output is correct
2 Correct 725 ms 51992 KB Output is correct
3 Correct 693 ms 53656 KB Output is correct
4 Correct 590 ms 53296 KB Output is correct
5 Correct 703 ms 50644 KB Output is correct
6 Correct 681 ms 51108 KB Output is correct
7 Correct 560 ms 54376 KB Output is correct