Submission #971738

#	Time	Username	Problem	Language	Result	Execution time	Memory
971738		tnknguyen_	Race (IOI11_race)	C++14	21 / 100	3043 ms	15708 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define endl '\n' 
#define pii pair<int, int>
//#define int long long 

const int MX = 2e5 + 5;
vector<pii> gr[MX];

void dfs(int u, int p, int sum, int cnt,int &ans, const int &k){
    if(sum > k){
        return;
    }
    if(sum == k){
        ans = min(ans, cnt);
    }
    for(pii e : gr[u]){
        int v, c;
        tie(v, c) = e;
        if(v != p){
            dfs(v, u, sum + c, cnt + 1, ans, k);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    int n = N;
    for(int i=0; i<n-1; ++i){
        int u = H[i][0], v = H[i][1], c = L[i];
        ++u, ++v;
        gr[u].push_back({v, c});
        gr[v].push_back({u, c});
    }

    int ans = 1e9;
    for(int i=1; i<=n; ++i){
        dfs(i, 0, 0, 0, ans, K);  
    }
    return (ans == 1e9 ? -1 : ans);
}

// int32_t main() {
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);
//     cout.tie(0);

//     freopen("main.inp","r",stdin);
//     freopen("main.out","w",stdout);

//     int n, k;
//     int h[20][2], l[20];
//     cin>>n>>k;
//     for(int i=0; i<n-1; ++i){
//         cin>>h[i][0]>>h[i][1]>>l[i];
//     }

//     cout<<best_path(n, k, h, l);

//     return 0;
// }

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