Submission #990709

#	Time	Username	Problem	Language	Result	Execution time	Memory
990709		vjudge1	Torrent (COI16_torrent)	C++17	31 / 100	5 ms	856 KiB

torrent

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

#define ll long long
int const N=1e3+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 ans=10000;
	for(int i=1;i<ab.size();i++){
		//erase edge
		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);
		ans=min(ans,max(dp[a],dp[b]));
		adj[u].insert(v);
		adj[v].insert(u);
	}
	cout<<ans<<endl;
	return 0;
}

Compilation message (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++)
      |              ~^~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:44:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i=1;i<ab.size();i++){
      |              ~^~~~~~~~~~

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