Submission #600512

#	Time	Username	Problem	Language	Result	Execution time	Memory
600512		Meloric	Race (IOI11_race)	C++14	21 / 100	3081 ms	26272 KiB

race

#include "race.h"
#include <iostream>
#include <vector>
#include <map>
 
#define int int64_t
 
using namespace std;
 
struct coll
{
	map<int,int> mp = 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: 0 / 22
• Subtask 4: 0 / 57