Submission #1100484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100484		sssamui	Race (IOI11_race)	C++17	9 / 100	82 ms	27516 KiB

race

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <algorithm>
using namespace std;
using ll = long long;

const int MXN = 2e5;

vector<vector<pair<int, ll>>> adj(MXN, vector<pair<int, ll>>(0));

vector<int> dep(MXN, 0);
vector<ll> dtr(MXN, 0);
vector<set<pair<ll, int>>> tmerg(MXN);

int ans = MXN;
int k;

void dfs(int node = 0, int p = -1)
{
	tmerg[node].insert({ dtr[node], dep[node] });
	for (pair<int, ll> nxt : adj[node]) if (nxt.first != p)
	{
		dep[nxt.first] = dep[node] + 1, dtr[nxt.first] = dtr[node] + nxt.second;
		dfs(nxt.first, node);

		bool cont = true;
		while ((!tmerg[nxt.first].empty()) && cont)
		{
			auto it = tmerg[nxt.first].end();
			it--;
			if ((*it).first - dtr[node] < k) cont = false;
			else
			{
				if ((*it).first - dtr[node] == k) ans = fmin(ans, (*it).second - dep[node]);
				tmerg[nxt.first].erase(it);
			}
		}

		if (tmerg[node].size() < tmerg[nxt.first].size()) swap(tmerg[node], tmerg[nxt.first]);
		for (pair<ll, int> tins : tmerg[nxt.first])
		{
			ll finddep = k - tins.first + 2 * dtr[node];
			auto it = tmerg[nxt.first].lower_bound({ finddep, 0 });
			if ((it != tmerg[nxt.first].end()) && ((*it).first == finddep)) ans = fmin(ans, (*it).second - 2 * dep[node] + tins.second);
		}

		for (pair<ll, int> tins : tmerg[nxt.first])
		{
			auto it = tmerg[node].lower_bound(tins);
			while ((it != tmerg[node].end()) && ((*it).first == tins.first))
			{
				tmerg[node].erase(it);
				it = tmerg[node].lower_bound(tins);
			}

			bool ins = true;
			if (it != tmerg[node].begin())
			{
				it--;
				if ((*it).first == tins.first) ins = false;
			}

			if (ins) tmerg[node].insert(tins);
		}

		tmerg[nxt.first].clear();
	}
}

int best_path(int N, int K, int H[][2], int L[])
{
	k = K;
	for (int i = 0; i < N - 1; i++) adj[H[i][0]].push_back({ H[i][1], L[i] }), adj[H[i][1]].push_back({ H[i][0], L[i] });
	dfs();
	if (ans == MXN) return -1;
	else return ans;
}

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