Submission #345069

#	Time	Username	Problem	Language	Result	Execution time	Memory
345069		daniel920712	경주 (Race) (IOI11_race)	C++14	21 / 100	3059 ms	11244 KiB

race

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

using namespace std;
long long ans=1000000000;
vector < pair < long long , long long > > Next[200005];
void F(long long fa,long long here,long long dis,long long deg,long long 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=0;i<N-1;i++)
    {
        Next[H[i][0]].push_back(make_pair((long long) H[i][1],(long long) L[i]));
        Next[H[i][1]].push_back(make_pair((long long) H[i][0],(long long) L[i]));
    }
    for(i=0;i<N;i++) F(-1,i,0,0,K);
    if(ans==1000000000) ans=-1;
    return (int) ans;
}

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