Submission #471231

#	Time	Username	Problem	Language	Result	Execution time	Memory
471231		PiejanVDC	Race (IOI11_race)	C++17	21 / 100	3067 ms	28748 KiB

race

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

int k, sum, cnt, best=INT_MAX;
vector<pair<int,int>>adj[1000000];

void dfs(int node, int e) {
	if(sum == k) {
		best=min(best,cnt);
		return;
	}
	for(auto a : adj[node]) {
		if(a.first == e || sum+a.second > k) continue;
		sum+=a.second;
		cnt++;
		dfs(a.first,node);
		cnt--;
		sum-=a.second;
	}
}

int best_path(int N, int K,int H[][2],int L[]) {
	k=K;
	for(int i = 0 ; i < N-1 ; i++) {
		adj[H[i][0]].push_back({H[i][1],L[i]});
		adj[H[i][1]].push_back({H[i][0],L[i]});
	}
	for(int root = 0 ; root < N ; root++) {
		sum=0;
		cnt=0;
		dfs(root,-1);
	}
	return (best==INT_MAX?-1:best);
}

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