제출 #990717

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
990717		vjudge1	Torrent (COI16_torrent)	C++17	100 / 100	1059 ms	53124 KiB

torrent

#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=3e5+5;
int const mod=1e9+7;

set<int> adj[N];
vector<int> path,ab;
int n,a,b;
int dp[N];
void dfs_dp(int node,int par){
	vector<int> v;
	for(auto i:adj[node]){
		if(i!=par){
			dfs_dp(i,node);
			v.push_back(dp[i]);
		}
	}
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	for(int i=0;i<v.size();i++)
		dp[node]=max(dp[node],v[i]+i+1);
}
void dfs(int node,int par){
	path.push_back(node);
	if(node==b)
		ab=path;
	for(auto i:adj[node])
		if(i!=par)
			dfs(i,node);
	path.pop_back();
}
int main(){
	cin>>n>>a>>b;
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		adj[u].insert(v);
		adj[v].insert(u);
	}
	dfs(a,0);
	int low=0,high=(ab.size())-1;
	while(high-low>1){
		int mid=(high+low)/2;
		int u=ab[mid],v=ab[mid+1];
	    adj[u].erase(v);
	    adj[v].erase(u);
	    for(int i=0;i<=n;i++)
	      dp[i]=0;
	    dfs_dp(a,0);
	    dfs_dp(b,0);
	    adj[u].insert(v);
	    adj[v].insert(u);
	    if(dp[a]<=dp[b])
	    	low=mid;
	    else
	    	high=mid;
	}
	int ans=10000000;
	for(int i=max(1,low-10);i<min(int(ab.size()),low+10);i++){
		int u=ab[i-1],v=ab[i];
	    adj[u].erase(v);
	    adj[v].erase(u);
	    for(int i=0;i<=n;i++)
	      dp[i]=0;
	    dfs_dp(a,0);
	    dfs_dp(b,0);
	    adj[u].insert(v);
	    adj[v].insert(u);
	    ans=min(ans,max(dp[a],dp[b]));
	}
	cout<<ans<<endl;
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

torrent.cpp: In function 'void dfs_dp(int, int)':
torrent.cpp:22:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i=0;i<v.size();i++)
      |              ~^~~~~~~~~

• Subtask 1: 31 / 31
• Subtask 2: 69 / 69