Submission #636539

#	Time	Username	Problem	Language	Result	Execution time	Memory
636539		gun_gan	Race (IOI11_race)	C++17	0 / 100	1 ms	340 KiB

race

#include <bits/stdc++.h>
using namespace std;

int best_path(int n, int k, int h[][2], int l[]) {
	vector<pair<int,int>> g[n];
	vector<int> deg(n);
	for(int i = 0; i < n - 1; i++) {
		g[h[i][0]].push_back({h[i][1], l[i]});
		g[h[i][1]].push_back({h[i][0], l[i]});
		deg[h[i][0]]++;
		deg[h[i][1]]++;
	}

	queue<pair<int,int>> q;
	vector<vector<int>> dist(n + 1, vector<int>(k + 1, -1)), par(n + 1, vector<int>(k + 1, -1));
	for(int i = 0; i < n; i++) {
		q.push({i, 0});
		dist[i][0] = 0;
	}
	
	while(!q.empty()) {
		auto [v, w] = q.front(); q.pop();
		// cout << v << " " << w << '\n';
		for(auto [u, c] : g[v]) {
			if(w + c <= k && dist[u][w + c] == -1 && u != par[v][w]) {
				dist[u][w + c] = dist[v][w] + 1;
				par[u][w + c] = v;
				q.push({u, w + c});
			}
		}
	}

	int ret = 1e9;
	for(int i = 0; i < n; i++) {
		// cout << dist[i][k] << '\n';
		if(dist[i][k] != -1) ret = min(ret, dist[i][k]);
	}

	return (ret == 1e9 ? -1 : ret);
}

// int main() {
// 	int n, k;
// 	cin >> n >> k;
// 	int h[n][2], l[n];
// 	for(int i = 0; i < n - 1; i++) {
// 		cin >> h[i][0] >> h[i][1];
// 	}
// 	for(int i = 0; i < n - 1; i++) {
// 		cin >> l[i];
// 	}
// 	cout << best_path(n, k, h, l) << '\n';

// }

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