Submission #345064

#	Time	Username	Problem	Language	Result	Execution time	Memory
345064		Kevin_Zhang_TW	Race (IOI11_race)	C++17	100 / 100	530 ms	83180 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;

	DE(x, dep, len);

	int res = inf;

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

	for (auto [u, w] : edge[x]) if (u != lst) {
		chmin(res, 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;
		nxt.clear();
	}
//	if (false) if (cur.count(k + len)) {
//		DE(dep, cur[k + len]);
//		chmin(res, cur[k + len] - dep);
//	}
	--dep;

	return res;
}

int best_path(int N, int K, int H[][2], int L[]) {
	static int cnt;
	assert(++cnt == 1);
	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;
}

Compilation message (stderr)

race.cpp: In function 'int dfs(int, int, ll)':
race.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
race.cpp:30:2: note: in expansion of macro 'DE'
   30 |  DE(x, dep, len);
      |  ^~

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