Submission #922098

#	Time	Username	Problem	Language	Result	Execution time	Memory
922098		Nurislam	Race (IOI11_race)	C++17	21 / 100	3029 ms	12116 KiB

race

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

using namespace std;

#define pb push_back

typedef vector<int> vi;
typedef vector<double> vd;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<vi> vv;

const int inf = 1e9, mod = 998244353;

struct gg{
	int ps, dp = 0, sm = 0, pr;
};
int best_path(int n, int k, int h[][2], int l[])
{
	vii g[n];
	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++){
		queue<gg> q;
		gg o;
		o.ps = i;
		o.dp = 0;
		o.sm = 0;
		o.pr = -1;
		q.push(o);
		while(!q.empty()){
			gg res = q.front();
			q.pop();
			if(res.sm > k)continue;
			if(res.sm == k){
				int cur = res.dp;
				ans = min(ans, cur);
				continue;
			}
			for(auto [to, cst]:g[res.ps]){
				if(to == res.pr)continue;
				gg nw;
				nw.ps = to;
				nw.pr = res.ps;
				nw.sm = res.sm+cst;
				nw.dp = res.dp+1;
				q.push(nw);
			}
		}
	}
	return (ans == inf?-1:ans);
}

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