Submission #209894

#	Time	Username	Problem	Language	Result	Execution time	Memory
209894		alishahali1382	Torrent (COI16_torrent)	C++14	31 / 100	147 ms	28536 KiB

torrent

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 500010;

int n, m, k, q, u, v, x, y, t, a, b, len;
int dp[MAXN];
bool on_path[MAXN];
vector<int> G[MAXN];
vector<int> path;

bool dfs_path(int node, int par){
	path.pb(node);
	if (node==b) return 1;
	for (int v:G[node]) if (v!=par && dfs_path(v, node)) return 1;
	path.pop_back();
	return 0;
}

int dfs_dp(int node, int par){
	vector<int> vec;
	for (int v:G[node]) if (!on_path[v] && v!=par) vec.pb(dfs_dp(v, node));
	sort(all(vec));
	reverse(all(vec));
	for (int i=0; i<vec.size(); i++) dp[node]=max(dp[node], vec[i]+i+1);
	return dp[node];
}

int check(int val){
	int cnt=0, tmp=val;
	for (int i=0; i<=len; i++){
		if (dp[path[i]]<tmp) tmp--, cnt++;
		else if (dp[path[i]]==tmp) {cnt++; break ;}
		else break ;
	}
	tmp=val;
	for (int i=len; i>=0; i--){
		if (dp[path[i]]<tmp) tmp--, cnt++;
		else if (dp[path[i]]==tmp) {cnt++; break ;}
		else break ;
	}

	return cnt>=len+1;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>a>>b;
	for (int i=1; i<n; i++){
		cin>>u>>v;
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs_path(a, a);
	len=path.size()-1;
	for (int v:path) on_path[v]=1;
	for (int v:path) dfs_dp(v, v);

	int dwn=-1, up=n;
	while (up-dwn>1){
		int mid=(dwn+up)>>1;
		if (check(mid)) up=mid;
		else dwn=mid;
	}
	cout<<up<<'\n';

	return 0;
}
/*
6 2 1
1 2
2 3
2 4
1 5
5 6


10 1 2
1 2
2 5
1 3
1 4
4 6
6 7
3 8
3 9
3 10


17 1 2
1 3
1 4
4 6
6 7
3 8
3 9
3 10
1 13
13 5
13 11
13 12
13 14
14 15
15 16
15 17
14 2

*/

Compilation message (stderr)

torrent.cpp: In function 'int dfs_dp(int, int)':
torrent.cpp:45:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<vec.size(); i++) dp[node]=max(dp[node], vec[i]+i+1);
                ~^~~~~~~~~~~

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