제출 #241634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241634		johutha	Race (IOI11_race)	C++17	100 / 100	488 ms	106372 KiB

race

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

#define int int64_t

using namespace std;

struct coll
{
	map<int,int>* mp = new map<int,int>();
	int offs = 0;

	bool operator<(const coll& c2)
	{
		return mp->size() < c2.mp->size();
	}

	void insert(int id, int v)
	{
		id -= offs;
		if (mp->find(id) != mp->end()) mp->at(id) = min(v, mp->at(id));
		else mp->insert(make_pair(id, v));
	}

	int query(int k)
	{
		k -= offs;
		if (mp->find(k) == mp->end()) return 1e7;
		return mp->at(k);
	}

	static int check(coll bs, coll nw, int k, int d)
	{
		if (bs < nw) swap(bs, nw);
		int mn = 1e7;

		for (auto p : (*nw.mp))
		{
			int ck = p.first + nw.offs;
			if (k < ck) continue;
			mn = min(mn, bs.query(k - ck) + p.second - 2*d);
		}
		return mn;
	}

	static coll merge(coll bs, coll nw)
	{
		if (bs < nw) swap(bs, nw);

		for (auto p : (*nw.mp))
		{
			bs.insert(p.first + nw.offs, p.second);
		}
		return bs;
	}
};

struct tree
{
	int n, k;
	vector<vector<pair<int,int>>> adjlist;
	int res = 1e7;

	coll dfs(int curr, int par, int d)
	{
		coll rt = coll();
		rt.insert(0, d);

		for (auto p : adjlist[curr])
		{
			if (p.first == par) continue;
			coll nt = dfs(p.first, curr, d + 1);
			nt.offs += p.second;
			res = min(res, coll::check(nt, rt, k, d));
			rt = coll::merge(nt, rt);
		}
		return rt;
	}
};

signed best_path(signed N, signed K, signed H[][2], signed L[])
{
	tree t;
	t.n = N;
	t.k = K;
	t.adjlist.resize(N);

	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.dfs(0, -1, 0);
	return (t.res >= N ? -1 : t.res);
}

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