Submission #1130442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130442		akzytr	Race (IOI11_race)	C++17	21 / 100	20 ms	1668 KiB

race

#include <bits/stdc++.h>
#define ve vector
#define ar array 
#define pb push_back
#define ins insert

#define endl '\n'
#define ll long long
using namespace std;

const int MXN = 1e3+1;
int K;
ve<pair<int, ll>> adj[MXN];

int dfs1(int x, int p, int need){
    if(need == 0){
        return 1;
    }
    if(need < 0){
        return 1e9;
    }
    int ans = 1e9;
    for(auto [i, c] : adj[x]){
        if(i != p){
            ans = min(ans, 1 + dfs1(i, x, need-c));
        }
    }
    return ans;
}

int dfs2(int x, int p){
    int ans = 1e9;
    for(auto [i, c] : adj[x]){
        if(i != p){
            ans = min(ans, dfs1(i, x, K-c));
        }
    }
    return ans;
}

int best_path(int N, int k, int H[][2], int L[]){
    K = k;
    for(int i = 0; i < N-1; i++){
        adj[H[i][0]].pb({H[i][1], L[i]});
        adj[H[i][1]].pb({H[i][0], L[i]});
    }
    int ans = 1e9;
    for(int i = 0; i < N; i++){
        ans = min(ans, dfs2(i, -1));
    }
    if(ans == 1e9){
        return -1;
    }
    else{
        return ans;
    }
}

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