Submission #345063

#	Time	Username	Problem	Language	Result	Execution time	Memory
345063		daniel920712	Race (IOI11_race)	C++14	9 / 100	3093 ms	11244 KiB

race

#include "race.h"
#include <vector>
#include <utility>

using namespace std;
int ans=1000000000;
vector < pair < int , int > > Next[200005];
void F(int fa,int here,int dis,int deg,int K)
{
    if(dis==K) ans=min(ans,deg);
    if(dis>=K) return ;
    for(auto i:Next[here]) if(i.first!=fa) F(here,i.first,dis+i.second,deg+1,K);
}
int best_path(int N, int K, int H[][2], int L[])
{
    int i;
    for(i=1;i<N;i++)
    {
        Next[H[i][0]].push_back(make_pair(H[i][1],L[i]));
        Next[H[i][1]].push_back(make_pair(H[i][0],L[i]));
    }
    for(i=0;i<N;i++) F(-1,i,0,0,K);
    if(ans==1000000000) ans=-1;
    return ans;
}

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