Submission #331131

#	Time	Username	Problem	Language	Result	Execution time	Memory
331131		prarie	Race (IOI11_race)	C++14	0 / 100	4 ms	5868 KiB

race

#include "race.h"

#include <bits/stdc++.h>
 
#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
#define fi first
#define se second
#define endl '\n'
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define compress(v) sort(all(v)), (v).erase(unique(all((v))), v.end())
 
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ld = long double;
 
const int N = 2e5 + 5;
const int K = 1e6 + 5;

int n, k;
vector<pii> adj[N];
bool fin[N];
int sz[N];
int d[K];

int get_cent(int t_size, int cur, int pv = -1) {
	int minx = N;
	for (auto &next : adj[cur]) {
		if (pv == next.first || fin[next.first]) continue;
		if (sz[next.first] > t_size / 2)
			return get_cent(t_size, next.first, cur);
		minx = min(minx, sz[next.first]);
	}
	if (minx <= t_size / 2) return cur;
	return -1;
}

void get_sz(int cur, int pv = -1) {
	sz[cur] = 1;
	for (auto &next : adj[cur]) {
		if (next.first == pv || fin[next.first]) continue;
		get_sz(next.first, cur);
		sz[cur] += sz[next.first];
	}
}

void assign(int cur, int w, int pv = -1, int cnt = 1) {
	if (w > k) return;
	d[w] = min(d[w], cnt);
	for (auto &next : adj[cur]) {
		if (next.first == pv || fin[next.first]) continue;
		assign(next.first, next.second + w, cur, cnt + 1);
	}
}

int get(int cur, int w, int pv = -1, int cnt = 1) {
	int ret = N;
	if (w > k) return ret;
	ret = min(ret, cnt + d[k - w]);
	for (auto &next : adj[cur]) {
		if (next.first == pv || fin[next.first]) continue;
		ret = min(get(next.first, w + next.second, cur, cnt + 1), ret);
	}
	return ret;
}

int calc(int node) {
	int ret = N;
	// Find Centroid
	memset(sz, 0, sizeof sz);
	get_sz(node);
	int cent = get_cent(sz[node], node);
	//cout << node << ' ' << cent << endl;
	if (cent == -1) {
		fin[node] = true;
		return ret;
	}

	fin[cent] = true;

	// Find Minimum nodes of length K
	memset(d, 0x3f, sizeof d);
	d[0] = 0;
	for (auto &next : adj[cent]) {
		if (fin[next.first]) continue;
		ret = min(ret, get(next.first, next.second));
		assign(next.first, next.second);
	}

	// call calc for subtrees
	for (auto &next : adj[cent]) {
		if (fin[next.first]) continue;
		ret = min(ret, calc(next.first));
	}
	return ret;
}

int best_path(int N, int K, int H[][2], int L[])
{
	n = N, k = K;
	for (int i = 1; i < N; i++) {
		int u = H[i][0], v = H[i][1], w = L[i];
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}
	return calc(0);
}

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