Submission #62073

#	Time	Username	Problem	Language	Result	Execution time	Memory
62073		aome	Race (IOI11_race)	C++17	100 / 100	1357 ms	85548 KiB

race

#include "race.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 200005;
const int M = 1000005;
const int INF = 0x3f3f3f3f;

int K;
int res = INF;
int sz[N], h[N];
int f[M];
long long d[N];
bool del[N];
vector<int> buf;
vector< pair<int, int> > G[N];

void add(int u, int v, int w) {
	G[u].push_back({v, w});
	G[v].push_back({u, w});
}

void dfs(int u, int p) {
	sz[u] = 1;
	buf.push_back(u);
	for (auto v : G[u]) {
		if (p == v.first || del[v.first]) continue;
		dfs(v.first, u), sz[u] += sz[v.first];
	}
}

int find(int u, int p, int r) {
	for (auto v : G[u]) {
		if (p == v.first || del[v.first]) continue;
		if (2 * sz[v.first] >= sz[r]) return find(v.first, u, r);
	}
	return u;
}

void query(int u, int p) {
	if (d[u] <= K) res = min(res, h[u] + f[K - d[u]]);
	for (auto v : G[u]) {
		if (p == v.first || del[v.first]) continue;
		h[v.first] = h[u] + 1, d[v.first] = d[u] + v.second;
		query(v.first, u);
	}
}

void add(int u, int p) {
	if (d[u] <= K) f[d[u]] = min(f[d[u]], h[u]);
	for (auto v : G[u]) {
		if (p == v.first || del[v.first]) continue;
		add(v.first, u);
	}
}

void solve(int u) {
	buf.clear(), dfs(u, u);
	u = find(u, u, u), del[u] = 1;
	d[u] = h[u] = f[0] = 0;
	for (auto v : G[u]) {
		if (del[v.first]) continue;
		d[v.first] = v.second, h[v.first] = 1;
		query(v.first, u), add(v.first, u);
	}
	for (auto i : buf) {
		if (d[i] <= K) f[d[i]] = INF;
	}
	for (auto v : G[u]) {
		if (del[v.first]) continue; solve(v.first);
	}
}

int best_path(int n, int _K, int H[][2], int L[]) {
	K = _K;
	for (int i = 0; i < (n - 1); ++i) {
		add(H[i][0], H[i][1], L[i]);
	}
	memset(f, INF, sizeof f);
	solve(0);
	return res == INF ? -1 : res;
}

Compilation message (stderr)

race.cpp: In function 'void solve(int)':
race.cpp:72:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if (del[v.first]) continue; solve(v.first);
   ^~
race.cpp:72:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   if (del[v.first]) continue; solve(v.first);
                               ^~~~~

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