Submission #92008

#	Time	Username	Problem	Language	Result	Execution time	Memory
92008		easrui	Race (IOI11_race)	C++14	21 / 100	3047 ms	11256 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int MN = 2e5+5;

struct Edge{
    int x,d;
    Edge(int a, int b){
        x = a;
        d = b;
    }
};

vector<Edge> T[MN];

int DFS(int i, int val, int dis, int r, int K){
    if(dis==K) return val;
    if(dis>K) return MN;
    int res = MN;
    for(auto it : T[i]){
        //cout << i << ' ' << it.x << ' ' << r << '\n';
        if(it.x==r) continue;
        res = min(res,DFS(it.x,val+1,dis+it.d,i,K));
    }
    return res;
}

int best_path(int N, int K, int H[][2], int L[])
{
    int ans = MN;
    for(int i=0; i<N-1; i++){
        T[H[i][0]].push_back(Edge(H[i][1],L[i]));
        T[H[i][1]].push_back(Edge(H[i][0],L[i]));
    }
    for(int i=0; i<N; i++){
        ans = min(ans,DFS(i,0,0,i,K));
    }
    if(ans==MN) ans = -1;
    return ans;
}

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