Submission #1274147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274147		almaz	Race (IOI11_race)	C++20	21 / 100	3094 ms	8200 KiB

race

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

// #define int long long
// #define endl '\n'
#define ff first
#define ss second
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ar array

const int MOD = 1e9 + 7,INF = 1e9, N = 2e5 + 5;


int best_path(int n, int k, int H[][2], int L[]){
	vector <vector <pair<int,int>>> g(n + 1);
	
	for(int i = 0;i < n - 1;i++){
		g[H[i][0]].pb({H[i][1] , L[i]});
		g[H[i][1]].pb({H[i][0] , L[i]});
	}
	
	int ans = INF;
	
	for(int i = 0;i < n;i++){
		vector <pair<int,int>> a(n , {INF, INF});
		a[i] = {0 , 0};
		
		priority_queue <int> q;
		
		q.push(i);
		
		while(!q.empty()){
			int x = q.top();
			q.pop();
			
			for(auto [j , c] : g[x]){
				if(a[j].ff != INF) continue;	
				a[j].ff = a[x].ff + c;
				a[j].ss = a[x].ss + 1;
				
				if(a[j].ff == k){
					ans = min(ans, a[j].ss);
				}
				if(a[j].ff < k){
					q.push(j);
				}
			}
		}
	}
	if(ans == INF) return -1;
	return ans;
}

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