Submission #50060

#	Time	Username	Problem	Language	Result	Execution time	Memory
50060		Diuven	Race (IOI11_race)	C++11	100 / 100	714 ms	33520 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int KMX=1000010, MX=200010, inf=2e9;
typedef pair<int, int> pii;

vector<pii> G[MX];
bool done[MX];

int sub[MX];

void init(int v, int par=-1){
	sub[v]=1;
	for(pii &p:G[v]){
		int x=p.first;
		if(done[x] || x==par) continue;
		init(x,v); sub[v]+=sub[x];
	}
}

int findcen(int v, int sz){
	for(pii &p:G[v]){
		int x=p.first;
		if(done[x] || sub[x]>sub[v]) continue;
		if(sub[x]*2>=sz) return findcen(x,sz);
	}
	return v;
}

int dist[KMX];
vector<pii> V, W;
int n, k;

void dfs(int v, int par=-1, int dep=0, int cnt=0){
	for(pii &p:G[v]){
		int x,c; tie(x,c)=p;
		if(x==par || done[x]) continue;
		dfs(x,v,dep+c,cnt+1);
	}
	if(0<dep && dep<=k){
		V.push_back({dep, cnt});
	}
}

int solve(int v){
	init(v); v=findcen(v, sub[v]); done[v]=true;
	int ans=inf;
	for(pii &p:G[v]){
		int x,c; tie(x,c)=p;
		if(done[x]) continue;
		dfs(x,v,c,1);

		// cutting?
		for(pii &q:V){
			int dep, cnt; tie(dep, cnt)=q;
			ans=min(ans, cnt+dist[k-dep]);
		}
		for(pii &q:V){
			int dep, cnt; tie(dep, cnt)=q;
			dist[dep]=min(dist[dep], cnt);
			W.push_back(q);
		}
		V.clear();
	}
	for(pii &q:W){
		int dep=q.first;
		dist[dep]=inf;
	}
	W.clear();
	for(pii &p:G[v]){
		int x=p.first;
		if(done[x]) continue;
		ans=min(solve(x), ans);
	}
	return ans;
}

int best_path(int N, int K, int H[][2], int L[]){
	n=N, k=K;
	for(int i=0; i<n-1; i++){
		int u=H[i][0], v=H[i][1], c=L[i];
		G[u].push_back({v,c});
		G[v].push_back({u,c});
	}
	fill(dist+1, dist+k+1, inf);
	int ans=solve(0);
	return ans>=inf/2 ? -1 : ans;
}

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