제출 #236744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236744		srvlt	경주 (Race) (IOI11_race)	C++14	100 / 100	696 ms	38520 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define ull unsigned long long
#define db long double
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define mp make_pair
#define all(x) (x).begin(), (x).end()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;

typedef tree <pii, null_type, less <pii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int max_N = 200003, max_K = 1000003, INF = 1e9;
int n, k, sz[max_N], mx[max_N], del[max_N], val[max_K], ans;
vector <pii> adj[max_N];

void dfs(int v, int p) {
	sz[v] = 1;
	mx[v] = -1;
	for (auto i : adj[v]) {
		int to = i.F;
		if (to == p || del[to]) {
			continue;
		}
		dfs(to, v);
		sz[v] += sz[to];
		if (mx[v] == -1 || sz[mx[v]] < sz[to]) {
			mx[v] = to;
		}
	}
}

int centroid(int v) {
	int u = v;
	while (mx[v] != -1 && sz[mx[v]] > sz[u] / 2) {
		v = mx[v];
	}
	return v;
}

void add(int v, int p, int d, int l) {
	if (d > k) {
		return;
	}
	val[d] = min(val[d], l);
	for (auto i : adj[v]) {
		int to = i.F, w = i.S;
		if (to == p || del[to]) {
			continue;
		}
		add(to, v, d + w, l + 1);
	}
}

void calc(int v, int p, int d, int l) {
	if (d > k) {
		return;
	}
	ans = min(ans, val[k - d] + l);
	for (auto i : adj[v]) {
		int to = i.F, w = i.S;
		if (to == p || del[to]) {
			continue;
		}
		calc(to, v, d + w, l + 1);
	}
}

void clear(int v, int p, int d, int l) {
	if (d > k) {
		return;
	}
	val[d] = INF;
	for (auto i : adj[v]) {
		int to = i.F, w = i.S;
		if (to == p || del[to]) {
			continue;
		}
		clear(to, v, d + w, l + 1);
	}
}

void solve(int v) {
	val[0] = 0;
	for (auto i : adj[v]) {
		int to = i.F, w = i.S;
		if (del[to]) {
			continue;
		}
		calc(to, v, w, 1);
		add(to, v, w, 1);
	}
	for (auto i : adj[v]) {
		int to = i.F, w = i.S;
		if (del[to]) {
			continue;
		}
		clear(to, v, w, 1);
	}
}

void build(int v, int d) {
	dfs(v, -1);
	int c = centroid(v);
	solve(c);
	del[c] = 1;
	for (auto i : adj[c]) {
		int to = i.F;
		if (!del[to]) {
			build(to, d + 1);
		}
	}
}

int best_path(int N, int K, int H[][2], int L[]) {
	n = N;
	k = K;
	memset(& del, 0, sizeof(del));
	for (int i = 0; i < n - 1; i++) {
		adj[i].clear();
	}
	ans = max_N;
	for (int i = 0; i < n - 1; i++) {
		adj[H[i][0]].pb({H[i][1], L[i]});
		adj[H[i][1]].pb({H[i][0], L[i]});
	}
	memset(& val, 0x3f, sizeof(val));
	build(0, 0);
	if (ans == max_N) {
		return -1;
	}
	return ans;
}

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