Submission #398070

#	Time	Username	Problem	Language	Result	Execution time	Memory
398070		Antekb	Race (IOI11_race)	C++14	21 / 100	3093 ms	130444 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];
map<ll, int> dist[N], dist2[N], opt[N];
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";
}
void dfs_calc(int v, int p, int anc){
	//cout<<v<<" "<<dep[v]<<" "<<d[v]<<"\n";
	if(dist[cent][d[v]]==0 || dist[cent][d[v]]>dep[v]){
		if(opt[cent][d[v]]!=anc)dist2[cent][d[v]]=dist[cent][d[v]];
		dist[cent][d[v]]=dep[v];
		opt[cent][d[v]]=anc;
	}
	if(dist[cent][k-d[v]]!=0 && opt[cent][k-d[v]]!=anc)ans=min(ans, dep[v]+dist[cent][k-d[v]]);
	if(dist2[cent][k-d[v]]!=0)ans=min(ans, dep[v]+dist2[cent][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];
			dfs_calc(to[i], v, anc);
		}
	}
}
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];
			dfs_calc(to[i], cent, to[i]);
		}
	}
	int C=cent;
	dist[C].clear();
	dist2[C].clear();
	opt[C].clear();
	dfs_siz(C, 0, n);
	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: 0 / 22
• Subtask 4: 0 / 57