Submission #416942

#	Time	Username	Problem	Language	Result	Execution time	Memory
416942		snasibov05	Race (IOI11_race)	C++14	21 / 100	3055 ms	7388 KiB

race

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

using namespace std;

#define oo 1000000000
#define pii pair<int, int>
#define pb push_back
#define f first
#define s second

int ans = oo;
vector<vector<pii>> ed;

void dfs(int cur, int pr, int l, int k, int d){
    if (l == k) {
        ans = min(ans, d);
        return;
    }

    for (auto to : ed[cur]){
        if (to.f == pr) continue;
        dfs(to.f, cur, l + to.s, k, d+1);
    }
}

int best_path(int n, int k, int h[][2], int l[]){
    ed.resize(n);
    for (int i = 0; i < n - 1; ++i) {
        ed[h[i][0]].pb({h[i][1], l[i]});
        ed[h[i][1]].pb({h[i][0], l[i]});
    }

    for (int i = 0; i < n; ++i){
        dfs(i, -1, 0, k, 0);
    }

    if (ans == oo) ans = -1;

    return ans;

}

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