Submission #636516

#	Time	Username	Problem	Language	Result	Execution time	Memory
636516		gun_gan	Race (IOI11_race)	C++17	0 / 100	0 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));
	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();
		for(auto [u, c] : g[v]) {
			if(w + c <= k && dist[u][w + c] == -1) {
				dist[u][w + c] = dist[v][w] + 1;
				q.push({u, w + c});
			}
		}
	}

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

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

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

// }

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