제출 #807216

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
807216		vjudge1	경주 (Race) (IOI11_race)	C++17	21 / 100	3066 ms	30720 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

const int maxn = 1e6 + 5;
const int inf = 1e9 + 7;

int depth[maxn];
int road[maxn];
int n, k;
vector<pair<int, int>> tr[maxn];

void dfs(int u, int p){
	for(auto node : tr[u]){
		int v = node.first;
		int w = node.second;
		if(v == p) continue;
		depth[v] = depth[u] + 1;
		road[v] = road[u] + w;
		dfs(v, u);
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	n = N;
	k = K;
	for(int i = 0; i < n - 1; i++){
		int a, b, l;
		a = H[i][0];
		b = H[i][1];
		l = L[i];
		tr[a].push_back({b, l});
		tr[b].push_back({a, l});
	}

	int result = inf;
	for(int i = 0; i < n; i++){
		depth[i] = 0;
		road[i] = 0;
		dfs(i, -1);
		for(int j = 0; j < n; j++){
			if(road[j] == k && result > depth[j]){
				result = depth[j];
			}
		}
	}

	if(result == inf){
		return -1;
	}else{
		return result;
	}
}

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