Submission #670573

#	Time	Username	Problem	Language	Result	Execution time	Memory
670573		mseebacher	Race (IOI11_race)	C++17	0 / 100	2 ms	2644 KiB

race

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
#define MAXI (int)1e5

vector<int> ad[MAXI];

int shortest = 1e9;
int len = 0;

map<pair<int,int>,int> paths;

void dfs(int x,int e,ll summe,int cnt){
	if(summe > len || cnt > shortest) return;
	if(summe == len){
		shortest = min(shortest,cnt);
		return;
	}
	for(auto s: ad[x]){
		if(s == e) continue;
		dfs(s,x,summe+paths[{x,s}],cnt+1);
	}
}

int best_path(int n, int k, int h[][2], int l[]){
	len = k;
	for(int i = 0;i<n-1;i++){
		int u = h[i][0];
		int v = h[i][1];
		ad[u].push_back(v);
		ad[v].push_back(u);
		paths.insert({{u,v},l[i]});
		paths.insert({{v,u},l[i]});
	}
	for(int i = 1;i<=n;i++){
		dfs(i,i,0,1);
	}
	if(shortest == 1e9) shortest = -1;
	return shortest-1;
}

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