Submission #345060

#	Time	Username	Problem	Language	Result	Execution time	Memory
345060		Kevin_Zhang_TW	Race (IOI11_race)	C++17	0 / 100	15 ms	21484 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a ? (a = b, true) : false; }
template<class T> bool chmax(T &a, T b) { return a < b ? (a = b, true) : false; }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010, inf = 1e9;

vector<pair<int,int>> edge[MAX_N];

map<ll,int> amp[MAX_N];

int k;

int dfs(int x, int lst = -1, ll len = 0) {
	static int dep;
	++dep;

	int res = inf;

	auto &cur = amp[x]; cur[len] = dep;

	for (auto [u, w] : edge[x]) if (u != lst) {
		dfs(u, x, len + w);
		auto &nxt = amp[u];
		if (cur.size() < nxt.size()) swap(cur, nxt);

		for (auto [L, D] : nxt) {
			if (cur.count(k + 2 * len - L))
				chmin(res, D + cur[k + 2 * len - L] - 2 * dep);
		}
		for (auto [L, D] : nxt)
			if (cur.count(L))
				chmin(cur[L], D);
			else cur[L] = D;
	}
	--dep;

	return res;
}

int best_path(int N, int K, int H[][2], int L[]) {
	for (int i = 0;i+1 < N;++i) {
		int a = H[i][0], b = H[i][1], w = L[i];
		edge[a].pb(b, w);
		edge[b].pb(a, w);
	}
	k = K;
	int res = dfs(0);
	return res == inf ? -1 : res;
}

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