oj.uz

Submission #971674

# Submission time Handle Problem Language Result Execution time Memory
971674 2024-04-29T07:25:28 Z tnknguyen_ Race (IOI11_race) C++14
21 / 100
 3000 ms 14672 KB 
#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){
        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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8792 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 2 ms 8776 KB Output is correct
17 Correct 2 ms 8540 KB Output is correct
18 Correct 2 ms 8540 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8792 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 2 ms 8776 KB Output is correct
17 Correct 2 ms 8540 KB Output is correct
18 Correct 2 ms 8540 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 2 ms 8540 KB Output is correct
21 Correct 8 ms 8796 KB Output is correct
22 Correct 8 ms 8816 KB Output is correct
23 Correct 9 ms 8796 KB Output is correct
24 Correct 8 ms 8796 KB Output is correct
25 Correct 7 ms 8792 KB Output is correct
26 Correct 7 ms 8784 KB Output is correct
27 Correct 8 ms 8796 KB Output is correct
28 Correct 7 ms 8796 KB Output is correct
29 Correct 7 ms 9048 KB Output is correct
30 Correct 8 ms 8816 KB Output is correct
31 Correct 7 ms 8796 KB Output is correct
32 Correct 8 ms 8792 KB Output is correct
33 Correct 8 ms 8792 KB Output is correct
34 Correct 9 ms 8828 KB Output is correct
35 Correct 10 ms 9052 KB Output is correct
36 Correct 7 ms 8796 KB Output is correct
37 Correct 7 ms 8796 KB Output is correct
38 Correct 8 ms 8836 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8792 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 2 ms 8776 KB Output is correct
17 Correct 2 ms 8540 KB Output is correct
18 Correct 2 ms 8540 KB Output is correct
19 Execution timed out 3011 ms 14672 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8792 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 2 ms 8776 KB Output is correct
17 Correct 2 ms 8540 KB Output is correct
18 Correct 2 ms 8540 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 2 ms 8540 KB Output is correct
21 Correct 8 ms 8796 KB Output is correct
22 Correct 8 ms 8816 KB Output is correct
23 Correct 9 ms 8796 KB Output is correct
24 Correct 8 ms 8796 KB Output is correct
25 Correct 7 ms 8792 KB Output is correct
26 Correct 7 ms 8784 KB Output is correct
27 Correct 8 ms 8796 KB Output is correct
28 Correct 7 ms 8796 KB Output is correct
29 Correct 7 ms 9048 KB Output is correct
30 Correct 8 ms 8816 KB Output is correct
31 Correct 7 ms 8796 KB Output is correct
32 Correct 8 ms 8792 KB Output is correct
33 Correct 8 ms 8792 KB Output is correct
34 Correct 9 ms 8828 KB Output is correct
35 Correct 10 ms 9052 KB Output is correct
36 Correct 7 ms 8796 KB Output is correct
37 Correct 7 ms 8796 KB Output is correct
38 Correct 8 ms 8836 KB Output is correct
39 Execution timed out 3011 ms 14672 KB Time limit exceeded
40 Halted 0 ms 0 KB -