Submission #241630

#	Time	Username	Problem	Language	Result	Execution time	Memory
241630		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;

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

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

		if (pths.find(w) == pths.end()) pths[w] = d;
		else pths[w] = min(d, pths[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();
		dfs(rt, -1, 0, 0, lvl[rt]);
	}
};

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