Submission #307398

#	Time	Username	Problem	Language	Result	Execution time	Memory
307398		juggernaut	Race (IOI11_race)	C++14	0 / 100	3084 ms	4992 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])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=0;i<k;i++){
        g[h[i][1]].push_back({h[i][0],l[i]});
        g[h[i][0]].push_back({h[i][1],l[i]});
    }
    for(i=0;i<n;i++)dfs(i,i,0,0);
    if(ans==inf)return -1;
    return ans;
}

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