oj.uz

Submission #209896

# Submission time Handle Problem Language Result Execution time Memory
209896 2020-03-15T22:36:26 Z alishahali1382 Torrent (COI16_torrent) C++14
100 / 100
 200 ms 63604 KB 
#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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 37624 KB Output is correct
2 Correct 28 ms 37624 KB Output is correct
3 Correct 29 ms 37624 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 56756 KB Output is correct
2 Correct 180 ms 61432 KB Output is correct
3 Correct 183 ms 60916 KB Output is correct
4 Correct 183 ms 63604 KB Output is correct
5 Correct 200 ms 62072 KB Output is correct
6 Correct 184 ms 61812 KB Output is correct
7 Correct 181 ms 62836 KB Output is correct