제출 #384072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
384072		Drew_	Race (IOI11_race)	C++14	0 / 100	8 ms	9728 KiB

race

#include "race.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ii pair<int, int>
#define f1 first
#define s2 second

const int MAX = 2e5 + 7;
const int inf = 1e9 + 7;

int n, k;
int sz[MAX];
set<ii> adj[MAX];
static int ans;

int get_sz(int node, int par)
{
	sz[node] = 1;
	for (ii to : adj[node])
		if (to.f1 != par)
			sz[node] += get_sz(to.f1, node);
	return sz[node];
}

int centroid(int node, int par, int n)
{
	for (ii to : adj[node])
		if (to.f1 != par && sz[to.f1] > n/2)
			return centroid(to.f1, node, n);
	return node;
}

//{distance, length, id
vector<pair<int, ii>> vec;
void dfs(int node, int par, int id, int dist, int h, bool zero)
{
	if (dist > k)
		return;

	if (!zero) //prevent duplicate data
		vec.pb({dist, {h, id}});

	for (ii to : adj[node])
	{
		if (to.f1 != par)
			dfs(to.f1, node, id, dist + to.s2, h+1, to.s2 == 0);
	}
}

void rc(int node)
{
	int n = get_sz(node, -1);
	int c = centroid(node, -1, n);
	vector<ii> edge(adj[c].begin(), adj[c].end());

	vec.clear();
	vec.pb({0, {0, 0}});

	int id = 1;
	for (ii e : edge)
		dfs(e.f1, c, id++, e.s2, 1, e.s2 == 0);

	sort(vec.begin(), vec.end());
	for (pair<int, ii> x : vec)
	{
		auto it = lower_bound(vec.begin(), vec.end(), mp(k - x.f1, mp(-1, -1)));
		if ((*it).s2.s2 == x.s2.s2)
			it = next(it);
		if ((*it).f1 != k-x.f1)
			continue;
		
		ans = min(ans, (*it).s2.f1 + x.s2.f1);
	}


	for (ii e : edge)
	{
		adj[c].erase(e);
		adj[e.f1].erase({c, e.s2});
		rc(e.f1);
	}
}

int best_path(int N, int K, int H[][2], int L[])
{
	n = N, k = K;
	for (int i = 0; i < N-1; ++i)
	{
		adj[H[i][0]].insert({H[i][1], L[i]});
		adj[H[i][1]].insert({H[i][0], L[i]});
	}

	ans = n;

	rc(0);
	return ans == n ? -1 : ans;
}

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