Submission #241493

#	Time	Username	Problem	Language	Result	Execution time	Memory
241493		johutha	Race (IOI11_race)	C++14	43 / 100	425 ms	132728 KiB

race

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

#define int __int128

using namespace std;
using rettype = pair<int,map<int,int>*>;

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

	tree(int in, int ik) : n(in), k(ik), res(n), adjlist(vector<vector<pair<int,int>>>(n)) {}
	
	void insert(rettype r1, int k, int v)
	{
		if (r1.second->count(k - r1.first)) (*r1.second)[k - r1.first] = min((*r1.second)[k - r1.first], v);
		else (*r1.second)[k - r1.first] = v;
	}

	int query(rettype rt, int q)
	{
		if (rt.second->count(q - rt.first)) return (*rt.second)[q - rt.first];
		else return 5*n;
	}

	rettype merge(rettype r1, rettype r2, int d)
	{
		if (r1.second->size() < r2.second->size()) swap(r1, r2);
		for (auto p : (*r2.second))
		{
			int ck = p.first + r2.first;
			res = min(res, query(r1, k - ck) + p.second - 2*d);
			insert(r1, ck, p.second);
		}
        return r1;
	}

	rettype dfs(int curr, int par, int d)
	{
		rettype ct = make_pair(0, new map<int,int>());
		insert(ct, 0, d);
		
		for (auto next : adjlist[curr])
		{
			if (next.first == par) continue;
			auto nt = dfs(next.first, curr, d + 1);
			nt.first += next.second;
			ct = merge(ct, nt, d);
		}
		res = min(query(ct, k) - d, res);
		return ct;
	}
};

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.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: 0 / 57