Submission #666569

#	Time	Username	Problem	Language	Result	Execution time	Memory
666569		si_jo	Race (IOI11_race)	C++14	0 / 100	1 ms	316 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

#define pb              push_back
#define vi              vector<int>
#define vvi			vector<vi>
#define pii             pair<int, int>
#define rep(i,a,b)      for(int i = a; i < b; i++)

int N, K, H[200010][2], L[200010];
int n, ans, k;
vi s, d, undo;
map<pii, int> wt;
void getsize(int cur, int par, vector<set<int>>& adj){
	s[cur] = 1;
	for(int a : adj[cur])	if(a != par){
		getsize(a, cur, adj);
		s[cur] += s[a];
	}
}

int centre(int cur, int par, vector<set<int>>& adj, int tot){
	for(int a : adj[cur])	if(a != par && s[a] > tot / 2)	return centre(a, cur, adj, tot);
	return cur;
}

void count(int cur, int par, vector<set<int>>& adj, bool f, int depth, int len){
	if(len > k)	return;
	if(f)	d[len] = min(d[len], depth);
	else	ans = min(ans, depth + d[k - len]);
	for(int a : adj[cur])	if(a != par)	count(a, cur, adj, f, depth + 1, len + wt[{a, cur}]);
}

void centroid(int cur, int par, vector<set<int>>& adj){
	getsize(cur, par, adj);
	int c = centre(cur, par, adj, s[cur]);
	for(int a : adj[c]){
		count(a, c, adj, 0, 1, wt[{a, c}]);
		count(a, c, adj, 1, 1, wt[{a, c}]);
	}
	ans = min(ans, d[k]);
	for(int i : undo)	d[i] = 1e9;
	undo.clear();
	for(int a : adj[c]){
		adj[a].erase(c);
		centroid(a, c, adj);
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	n = N, k = K; s.resize(n + 1); d.assign(k + 1, 1e9);
	ans = n;
	vector<set<int>> adj(n + 1);
	rep(i, 0, n - 1){
		int u = H[i][0] + 1, v = H[i][1] + 1;
		adj[u].insert(v); adj[v].insert(u);
		wt[{u, v}] = wt[{v, u}] = L[i];
	}
	centroid(1, 0, adj);
	return (ans == n ? -1 : ans);
}

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