Submission #398072

#	Time	Username	Problem	Language	Result	Execution time	Memory
398072		Antekb	Race (IOI11_race)	C++14	100 / 100	1051 ms	48420 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
const int N=2e5+5;
vi w, to, uzy;
vi E[N];
int siz[N], dep[N];
ll d[N];
const int M=1e6+5;
int dist[M], dist2[M], opt[M];
int k, cent, ans=N;
void dfs_siz(int v, int p, int n){
	siz[v]=1;
	bool czy=1;
	for(int i:E[v]){
		if(to[i]!=p && !uzy[i]){
			dfs_siz(to[i], v, n);
			siz[v]+=siz[to[i]];
			if(2*siz[to[i]]>n)czy=0;
		}
	}
	if(2*(n-siz[v])>n)czy=0;
	if(czy)cent=v;
	//cout<<v<<" "<<siz[v]<<"\n";
}
int dfs_calc(int v, int p, int anc){
	//cout<<v<<" "<<dep[v]<<" "<<d[v]<<"\n";
	int res=1;
	if(d[v]<=k && (dist[d[v]]==0 || dist[d[v]]>dep[v])){
		if(opt[d[v]]!=anc)dist2[d[v]]=dist[d[v]];
		dist[d[v]]=dep[v];
		opt[d[v]]=anc;
	}
	if(k>=d[v] && dist[k-d[v]]!=0 && opt[k-d[v]]!=anc)ans=min(ans, dep[v]+dist[k-d[v]]);
	if(k>=d[v] && dist2[k-d[v]]!=0)ans=min(ans, dep[v]+dist2[k-d[v]]);
	if(k==d[v])ans=min(ans, dep[v]);
	for(int i:E[v]){
		if(to[i]!=p && !uzy[i]){
			dep[to[i]]=dep[v]+1;
			d[to[i]]=d[v]+w[i];
			res+=dfs_calc(to[i], v, anc);
		}
	}
	return res;
}
void dfs_clear(int v, int p){
	if(d[v]<=k){
		dist[d[v]]=dist2[d[v]]=opt[d[v]]=0;
	}
	for(int i:E[v]){
		if(!uzy[i] && to[i]!=p){
			dfs_clear(to[i], v);
		}
	}
}
void decomp(int v, int n){
	//cout<<v<<" "<<n<<"a\n";
	if(n==1)return;
	cent=-1;
	dfs_siz(v, 0, n);
	assert(cent>0);
	//cout<<cent<<"\n";
	for(int i:E[cent]){
		if(!uzy[i]){
			dep[to[i]]=1;
			d[to[i]]=w[i];
			siz[to[i]]=dfs_calc(to[i], cent, to[i]);
		}
	}
	int C=cent;
	dfs_clear(C, 0);
	for(int i:E[C]){
		if(!uzy[i]){
			uzy[i]=1;
			uzy[i^1]=1;
			decomp(to[i], siz[to[i]]);
		}
	}
}
int best_path(int n, int _k, int H[][2], int L[])
{
	k=_k;
	for(int i=0; i<n-1; i++){
		H[i][0]++;
		H[i][1]++;
		E[H[i][0]].pb(to.size());
		to.pb(H[i][1]);
		E[H[i][1]].pb(to.size());
		to.pb(H[i][0]);
		w.pb(L[i]);
		w.pb(L[i]);
	}
	uzy.resize(w.size());
	decomp(1, n);
	return ((ans==N) ? -1 : ans);
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57