제출 #241633

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241633		johutha	경주 (Race) (IOI11_race)	C++17	0 / 100	5 ms	384 KiB

race

#include "race.h"
#include <iostream>
#include <vector>
#include <map>

#define int int64_t

using namespace std;

struct tree
{
	int n, k;
	int res;
	vector<vector<pair<int,int>>> adjlist;
	vector<int> sz;
	vector<int> lvl;

	tree(int in, int ik) : n(in), k(ik), res(2*n), adjlist(vector<vector<pair<int,int>>>(n)), sz(vector<int>(n)), lvl(vector<int>(n, 2*n)) {}

	int sdfs(int curr, int par, int l)
	{
		sz[curr] = 1;

		for (auto np : adjlist[curr])
		{
			int next = np.first;
			if (next == par) continue;
			if (lvl[next] < l) continue;
			sz[curr] += sdfs(next, curr, l);
		}
		return sz[curr];
	}

	int centroid(int curr, int par, int tots, int l)
	{
		for (auto np : adjlist[curr])
		{
			int next = np.first;
			if (next == par) continue;
			if (lvl[next] < l) continue;
			if (sz[next] > tots / 2) return centroid(next, curr, tots, l);
		}
		return curr;
	}

	void decomposition(int rt, int l)
	{
		sdfs(rt, -1, l);
		int cnt = centroid(rt, -1, sz[rt], l);
		lvl[cnt] = l;
		for (auto np : adjlist[cnt])
		{
			int next = np.first;
			if (lvl[next] > l) decomposition(next, l + 1);
		}
	}

	map<int,int> pths;
	map<int,int> newp;

	void dfs(int curr, int par, int w, int d, int l)
	{
		if (d != 0 && lvl[curr] <= l) return;

		if (w <= k && pths.find(k - w) != pths.end())
		{
			res = min(res, d + pths[k - w]);
		}

		if (newp.find(w) == newp.end()) newp[w] = d;
		else newp[w] = min(d, newp[w]);

		for (auto np : adjlist[curr])
		{
			int next = np.first;
			if (next != par) dfs(next, curr, w + np.second, d + 1, l);
		}
	}

	void check(int rt)
	{
		pths.clear();
		for (auto np : adjlist[rt])
		{
			if (lvl[np.first] <= lvl[rt]) continue;
			newp.clear();
			dfs(np.first, rt, np.second, 1, lvl[rt]);
			for (auto p : newp)
			{
				if (pths.find(p.first) == pths.end()) pths[p.first] = p.second;
				else pths[p.first] = min(p.second, pths[p.first]);
			}
		}
	}
};

signed best_path(signed N, signed K, signed H[][2], signed L[])
{
	tree t(N, K);

	for (int i = 0; i < N - 1; i++)
	{
		t.adjlist[H[i][0]].emplace_back(H[i][1], L[i]);
		t.adjlist[H[i][1]].emplace_back(H[i][0], L[i]);
	}

	t.decomposition(0, 0);

	for (int i = 0; i < N; i++) t.check(i);
	return (t.res >= N ? -1 : t.res);
}

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