Submission #226760

#	Time	Username	Problem	Language	Result	Execution time	Memory
226760		staniewzki	Race (IOI11_race)	C++17	100 / 100	1154 ms	42872 KiB

race

#include<bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
ostream& operator<<(ostream &out, string str) {
	for(char c : str) out << c;
	return out;
}
 
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
	return out << "(" << p.ST << ", " << p.ND << ")";
}
 
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
	out << "{";
	for(auto it = a.begin(); it != a.end(); it = next(it))
		out << (it != a.begin() ? ", " : "") << *it;
	return out << "}";
}
 
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
	cerr << a << ", ";
	dump(x...);
}
 
#ifdef DEBUG
#  define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#  define debug(...) false
#endif
 
template<class T> int size(T && a) { return (int) a.size(); }
 
using LL = long long;
using PII = pair<int, int>;

#include "race.h"

int best_path(int n, int k, int h[][2], int l[]) {
	vector<vector<PII>> adj(n);
	REP(i, n - 1) {
		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:54:18: warning: unused variable 'w' [-Wunused-variable]
   for(auto &[u, w] : adj[v]) {
                  ^
race.cpp: In lambda function:
race.cpp:66:18: warning: unused variable 'w' [-Wunused-variable]
   for(auto &[u, w] : adj[v]) {
                  ^
race.cpp: In lambda function:
race.cpp:102: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