Submission #782745

#	Time	Username	Problem	Language	Result	Execution time	Memory
782745		dozer	Race (IOI11_race)	C++14	0 / 100	7 ms	9980 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define M 200005


vector<pii> adj[M];
int sz[M], dep[M], dist[M], vis[M], mini[1000006];
int k, n, ans = M;

void dfs(int node, int root){
	sz[node] = 1;
	//cout<<node<<endl;
	for (auto i : adj[node]){
		if (i.st == root || vis[i.st]) continue;
		dfs(i.st, node);
		sz[node] += sz[i.st];
	}
}

void dfs2(int node, int root, int d, int dd, vector<pii> &all){
	all.pb({dd, d});
	for (auto i : adj[node]){
		if (i.st == root || vis[i.st]) continue;
		dfs2(i.st, node, d + 1, dd + i.nd, all);
	}
}

int find_centroid(int node, int root, int S){
	for (auto i : adj[node]){
		if (i.st == root || vis[i.st]) continue;
		if (sz[i.st] >= S / 2) return find_centroid(i.st, node, S);
	}
	return node;
}

void f(int node){
	dfs(node, 0);
	//cout<<sz[node]<<endl;
	node = find_centroid(node, 0, sz[node]);
	//cout<<"->"<<node<<endl;
	vector<pii> v;
	for (auto i : adj[node]){
		if (vis[i.st]) continue;
		vector<pii> tmp;
		dfs2(i.st, node, 1, i.nd, tmp);
		for (auto j : tmp){
			if (j.st <= k) ans = min(ans, mini[k - j.st] + j.nd);
		}
		for (auto j : tmp){
			mini[j.st] = min(mini[j.st], j.nd);
		}
		for (auto j : tmp)
		{
			v.pb(j);
		}
	}

	for (auto i : v){
		mini[i.st] = M;
	}

	vis[node] = 1;
	for (auto i : adj[node]){
		if (vis[i.st] == 0) f(i.st);
	}
}


int best_path(int N, int K, int H[][2], int L[]){
	k = K, n = N;

	for (int i = 0; i < N - 1; i++){
		int u = H[i][0] + 1, v = H[i][1] + 1;
		//cout<<u<<sp<<v<<endl;
		adj[u].pb({v, L[i]});
		adj[v].pb({u, L[i]});
	}

	for (int i = 1; i <= K; i++) mini[i] = M;

	f(1);
	if (ans < M)
		return ans;
	return -1;
}

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