Submission #226761

#	Time	Username	Problem	Language	Result	Execution time	Memory
226761		staniewzki	Race (IOI11_race)	C++17	100 / 100	1138 ms	39928 KiB

race

#include<bits/stdc++.h>
using namespace std;
 
#include "race.h"

int best_path(int n, int k, int h[][2], int l[]) {
	vector<vector<pair<int, int>>> adj(n);
	for(int i = 0; i < n - 1; i++) {
		adj[h[i][0]].emplace_back(h[i][1], l[i]);
		adj[h[i][1]].emplace_back(h[i][0], l[i]);
	}

	vector<int> sub(n), del(n);
	function<void(int, int)> get_sub = [&](int v, int p) {
		sub[v] = 1;
		for(auto &[u, w] : adj[v]) {
			if(u != p && !del[u]) {
				get_sub(u, v);
				sub[v] += sub[u];
			}
		}
	};

	function<int(int, int, int)> get_centro = [&](int v, int p, int tree) {
		bool is_centro = true;
		if((tree - sub[v]) * 2 > tree)
			is_centro = false;
		for(auto &[u, w] : adj[v]) {
			if(u != p && !del[u]) {
				int r = get_centro(u, v, tree);
				if(r != -1) return r;
				if(sub[u] * 2 > tree) 
					is_centro = false;
			}
		}
		if(is_centro) return v;
		return -1;
	};

	int inf = 1e9, ans = inf;
	vector<int> opt(k + 1, inf);

	function<void(int, int, int, int, int)> get_ans = [&](int v, int p, int dep, int dst, int type) {
		if(dst > k) return;
		if(type == 1) ans = min(ans, dep + opt[k - dst]);
		if(type == 2) opt[dst] = min(opt[dst], dep);
		if(type == 3) opt[dst] = inf;
		for(auto &[u, w] : adj[v])
			if(u != p && !del[u])
				get_ans(u, v, dep + 1, dst + w, type);
	};

	function<void(int)> decomp = [&](int v) {
		get_sub(v, -1);
		v = get_centro(v, -1, sub[v]);
		opt[0] = 0;
		for(auto &[u, w] : adj[v]) if(!del[u]) {
			get_ans(u, v, 1, w, 1);
			get_ans(u, v, 1, w, 2);
		}
		for(auto &[u, w] : adj[v]) if(!del[u])
			get_ans(u, v, 1, w, 3);
		del[v] = true;
		for(auto &[u, w] : adj[v]) if(!del[u])
			decomp(u);
	};

	decomp(0);
	if(ans >= inf) ans = -1;
	return ans;
}

Compilation message (stderr)

race.cpp: In lambda function:
race.cpp:16:18: warning: unused variable 'w' [-Wunused-variable]
   for(auto &[u, w] : adj[v]) {
                  ^
race.cpp: In lambda function:
race.cpp:28:18: warning: unused variable 'w' [-Wunused-variable]
   for(auto &[u, w] : adj[v]) {
                  ^
race.cpp: In lambda function:
race.cpp:64:18: warning: unused variable 'w' [-Wunused-variable]
   for(auto &[u, w] : adj[v]) if(!del[u])
                  ^

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