Submission #209896

#	Time	Username	Problem	Language	Result	Execution time	Memory
209896		alishahali1382	Torrent (COI16_torrent)	C++14	100 / 100	200 ms	63604 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;
#define SZ(x) ((int)x.size())

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];
int ptr[MAXN];
vector<int> G[MAXN];
vector<int> path;
vector<int> child[MAXN];
vector<int> mx[MAXN];

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;
}

bool cmp(int i, int j){ return dp[i]>dp[j];}

int dfs_dp(int node, int par){
	for (int v:G[node]) if (!on_path[v] && v!=par) dfs_dp(v, node), child[node].pb(v);
	if (child[node].empty()) return 0;
	sort(all(child[node]), cmp);
	mx[node].resize(child[node].size());
	mx[node][child[node].size()-1]=dp[child[node].back()]+child[node].size();
	for (int i=((int)child[node].size())-2; i>=0; i--) mx[node][i]=max(mx[node][i+1], dp[child[node][i]]+i+1);
	for (int i=((int)child[node].size())-1; i>=0; i--) mx[node][i]-=i;
	
	for (int i=0; i<((int)child[node].size()); i++) dp[node]=max(dp[node], dp[child[node][i]]+i+1);
	return dp[node];
}

int check(int val){
	memset(ptr, 0, sizeof(ptr));
	int cnt=0, tmp=val;
	for (int i=0; i<=len; i++){
		int v=path[i];
		while (ptr[v]<SZ(mx[v]) && mx[v][ptr[v]]==tmp){ tmp--; ptr[path[i]]++;}
		if (ptr[v]<SZ(mx[v]) && mx[v][ptr[v]]>tmp){ break ;}
		if (tmp>=0) cnt++;
		if (tmp<=0) break ;
		tmp--;
	}
	memset(ptr, 0, sizeof(ptr));
	tmp=val;
	for (int i=len; i>=0; i--){
		int v=path[i];
		while (ptr[v]<SZ(mx[v]) && mx[v][ptr[v]]==tmp){ tmp--; ptr[path[i]]++;}
		if (ptr[v]<SZ(mx[v]) && mx[v][ptr[v]]>tmp){ break ;}
		if (tmp>=0) cnt++;
		if (tmp<=0) break ;
		tmp--;
	}
	
	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=2*n;	
	while (up-dwn>1){
		int mid=(dwn+up)>>1;
		if (check(mid)) up=mid;					
		else dwn=mid;
	}
	cout<<up<<'\n';
	
	return 0;
}

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