Submission #499801

#	Time	Username	Problem	Language	Result	Execution time	Memory
499801		HappyPacMan	Race (IOI11_race)	C++14	21 / 100	3071 ms	9716 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 15;
vector<pair<int,int> > adj[MAXN];
int res = MAXN;

void dfs(int u,int p,long long k,long long d,int l){
    if(d == k) res = min(res,l);
    for(auto v : adj[u]){
        if(v.first == p) continue;
        dfs(v.first,u,k,d+v.second,l+1);
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    for(int i=0;i<N-1;i++){
        adj[H[i][0]].emplace_back(H[i][1],L[i]);
        adj[H[i][1]].emplace_back(H[i][0],L[i]);
    }
    for(int i=0;i<N;i++) dfs(i,i,K,0,0);
    if(res == MAXN) res = -1;
    return res;
}

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