Submission #1100485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100485		sssamui	Race (IOI11_race)	C++17	100 / 100	393 ms	108668 KiB

race

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#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<map<ll, int>> tmerg(MXN);

int ans = MXN;
int k;

void dfs(int node = 0, int p = -1)
{
	tmerg[node][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);
		if (tmerg[node].size() < tmerg[nxt.first].size()) swap(tmerg[node], tmerg[nxt.first]);
		for (pair<ll, int> tins : tmerg[nxt.first]) if (tmerg[node].count(k - tins.first + 2 * dtr[node]) == 1) ans = fmin(ans, tins.second - 2 *
			dep[node] + tmerg[node][k - tins.first + 2 * dtr[node]]);
		for (pair<ll, int> tins : tmerg[nxt.first]) if ((tmerg[node].count(tins.first) == 0) || (tmerg[node][tins.first] > tins.second))
			tmerg[node][tins.first] = tins.second;
	}
}

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: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57