Submission #263364

#	Time	Username	Problem	Language	Result	Execution time	Memory
263364		maximath_1	Race (IOI11_race)	C++11	100 / 100	697 ms	34296 KiB

race

#include "race.h"
#include <vector>
#include <bitset>
using namespace std;

vector<pair<int, int> > adj[200005];
int dp[1000005], path[1000005], sz[200005];
int n, k, ans = -1, centroid, mxnode, cnt = 0;
bitset<200005> vis;

int dfs_subtree(int nw, int bf){
	sz[nw] = 1;
	for(pair<int, int> nx : adj[nw])
		if(!vis[nx.first] && nx.first != bf)
			sz[nw] += dfs_subtree(nx.first, nw);
	return sz[nw];
}

void centroid_decomp(int nw, int bf, int all){
	int rs = all - sz[nw];
	for(pair<int, int> nx : adj[nw]) 
		if(!vis[nx.first] && nx.first != bf){
			centroid_decomp(nx.first, nw, all);
			rs = max(rs, sz[nx.first]);
		}
	if(rs < mxnode){
		centroid = nw;
		mxnode = rs;
	}
}

void dfs(int nw, int bf, int cst, int edge, bool fill){
	if(cst > k) return;
	if(!fill){
		if(dp[k - cst] == cnt && (edge + path[k - cst] < ans || ans == -1))
			ans = edge + path[k - cst];
		if(cst == k && (edge < ans || ans == -1))
			ans = edge;
	}else if(dp[cst] < cnt  || edge < path[cst]){
		dp[cst] = cnt;
		path[cst] = edge;
	}

	for(pair<int, int> nx : adj[nw]) if(!vis[nx.first] && nx.first != bf)
		dfs(nx.first, nw, cst + nx.second, edge + 1, fill);
}

void solve(int nw){
	cnt ++;
	if(dfs_subtree(nw, -1) <= 1) return;
	mxnode = sz[nw] + 1;
	centroid_decomp(nw, -1, sz[nw]);
	for(pair<int, int> nx : adj[centroid]) if(!vis[nx.first]){
		dfs(nx.first, centroid, nx.second, 1, false);
		dfs(nx.first, centroid, nx.second, 1, true);
	}
	vis[centroid] = 1;
	for(pair<int, int> nx : adj[centroid]) if(!vis[nx.first])
		solve(nx.first);
}

int best_path(int N, int K, int H[][2], int L[]){
	n = N; k = K;
	for(int i = 1; i < n; i ++){
		adj[H[i - 1][0]].push_back({H[i - 1][1], L[i - 1]});
		adj[H[i - 1][1]].push_back({H[i - 1][0], L[i - 1]});
	}

	solve(0);
	return ans;
}

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