제출 #307404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
307404		juggernaut	경주 (Race) (IOI11_race)	C++14	21 / 100	3083 ms	11256 KiB

race

#include"race.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>g[200005];
int k,i,inf=2e9,ans=inf;
void dfs(int v,int p,int depth,int val){
    if(val==k)ans=min(ans,depth);
    if(val>=k)return;
    for(auto to:g[v])if(to.first!=p)dfs(to.first,v,depth+1,val+to.second);
}
int best_path(int n,int K,int h[][2],int l[]){
    k=K;
    for(i=1;i<n;i++){
        g[h[i-1][1]].push_back({h[i-1][0],l[i-1]});
        g[h[i-1][0]].push_back({h[i-1][1],l[i-1]});
    }
    for(i=0;i<n;i++)dfs(i,i,0,0);
    if(ans==inf)return -1;
    return ans;
}

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