제출 #636505

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
636505		gun_gan	경주 (Race) (IOI11_race)	C++17	9 / 100	101 ms	51332 KiB

race

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

const int N = 2e5 + 5;
vector<pair<int,int>> g[N];
int dp[N][105], deg[N];

void dfs(int v, int p) {
	for(auto [u, c] : g[v]) {
		if(u == p) continue;
		for(int j = 0; j <= 100; j++) {
			if(j + c <= 100) {
				dp[u][j + c] = min(dp[u][j + c], dp[v][j] + 1);
			}
		}
		dfs(u, v);
	}
}

int best_path(int n, int k, int h[][2], int l[]) {
	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]]++;
	}

	for(int i = 0; i < n; i++) {
		for(int j = 1; j <= 100; j++) {
			dp[i][j] = 1e9;
		}
	}

	int root = 0;
	for(int i = 0; i < n; i++) {
		if(deg[i] == 1) {
			root = i;
			break;
		}
	}

	dfs(root, -1);

	int ret = 1e9;
	for(int i = 0; i < n; i++) ret = min(ret, dp[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: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57