oj.uz

Submission #1035971

# Submission time Handle Problem Language Result Execution time Memory
1035971 2024-07-26T22:14:51 Z andrewp Race (IOI11_race) C++14
0 / 100
 6 ms 14520 KB 
#include "race.h"
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
using ll = int64_t;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dbg(x) cerr << #x << ": " << x << '\n';

const int N = 2e5 + 20, INF = 1e9 + 20;
int n, price[N], dep[N];
int k, ans = INF;
vector<pii> g[N];
map<int, int> mp[N];

void build(int x, int par, int pr, int d) {
	price[x] = pr, dep[x] = d;
	for (auto u : g[x]) {
		if (u.first != par) {
			build(u.first, x, pr + u.second, d + 1);
		}
	}
}

void dfs(int x, int par) {
	mp[x][price[x]] = dep[x];
	for (auto u : g[x]) {
		if (u.first != par) {
			dfs(u.first, x);
			if (mp[u.first].size() > mp[x].size()) {
				mp[x].swap(mp[u.first]);
			}
			for (auto add : mp[u.first]) {
				int calc = 2 * price[x] + k - add.first;
				if (mp[x].count(calc)) {
					ans = min(ans, mp[x][calc] + add.second - 2 * dep[x]);
				}
			}
			for (auto add : mp[u.first]) {
				if (mp[x].count(add.first)) {
					mp[x][add.first] = min(mp[x][add.first], add.second);
				} else {
					mp[x][add.first] = add.second;
				}
			}
			if (mp[x].count(k + price[x])) {
				ans = min(ans, mp[x][k + price[x]] - dep[x]);
			}
		}
	}
	// if (x == 1) dbg(mp[x].count(2));
}

int best_path(int NN, int K, int H[][2], int LEN[]) {
	n = NN, k = K;
	for (int i = 0; i < n - 1; i++) {
		int u = H[i][0];
		int v = H[i][1];
		int w = LEN[i];
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	dep[0] = 0, price[0] = 0;
	build(0, -1, 0, 0);
	// for (int i = 0; i < n; i++) cerr << price[i] << ' ';
	// cout << '\n';
	dfs(0, -1);
	return ans;
}

// int32_t main() {
// 	ios::sync_with_stdio(false); cin.tie(nullptr);
// 	cout.tie(nullptr); cerr.tie(nullptr);
//
// 	int NN, K;
// 	cin >> NN >> K;
//
// 	int H[NN][2], LEN[NN];
//
// 	for (int i = 0; i < NN - 1; i++) {
// 		cin >> H[i][0] >> H[i][1];
// 	}
// 	for (int i = 0; i < NN - 1; i++) {
// 		cin >> LEN[i];
// 	}
// 	int ans = best_path(NN, K, H, LEN);
// 	cout << "Solution: " << (ans == INF ? -1 : ans) << '\n';
// }

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Incorrect 6 ms 14520 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Incorrect 6 ms 14520 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Incorrect 6 ms 14520 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Incorrect 6 ms 14520 KB Output isn't correct
4 Halted 0 ms 0 KB -