oj.uz

Submission #1005245

# Submission time Handle Problem Language Result Execution time Memory
1005245 2024-06-22T09:18:02 Z cpdreamer Race (IOI11_race) C++17
9 / 100
 82 ms 185936 KB 
#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define P pair
#define V vector
#define F first
#define S second
#define pb push_back
typedef long long ll;
ll dp[(ll)200001][110];
void dfs(ll n,ll p,V<P<ll,ll>>tree[],ll k){
    dp[n][0]=0;
    for(auto u:tree[n]){
        if(u.F==p)continue;
        dfs(u.F,n,tree,k);
        for(ll i=u.S;i<=k;i++){
            if(dp[u.F][i-u.S]!=-1){
                if(dp[n][i]!=-1)
                    dp[n][i]=min(dp[n][i],dp[u.F][i-u.S]+1);
                else
                    dp[n][i]=dp[u.F][i-u.S]+1;
            }
        }
    }
}
int best_path(int  N, int K, int H[][2], int L[])
{
    memset(dp,-1,sizeof(dp));
    V<P<ll,ll>>tree[N];
    for(ll i=0;i<N-1;i++){
        tree[H[i][0]].pb({H[i][1],L[i]});
        tree[H[i][1]].pb({H[i][0],L[i]});
    }
    dfs(0,-1,tree,K);
    ll ans=-1;
    for(ll i=0;i<N;i++){
        if(dp[i][K]!=-1) {
            if(ans!=-1)
                ans = min(dp[i][K], ans);
            else
                ans=dp[i][K];
        }
    }
    return (int)ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 176208 KB Output is correct
2 Correct 22 ms 176220 KB Output is correct
3 Correct 22 ms 176288 KB Output is correct
4 Correct 23 ms 176220 KB Output is correct
5 Correct 24 ms 176060 KB Output is correct
6 Correct 22 ms 176220 KB Output is correct
7 Correct 21 ms 176208 KB Output is correct
8 Correct 23 ms 176220 KB Output is correct
9 Correct 23 ms 176284 KB Output is correct
10 Correct 22 ms 176196 KB Output is correct
11 Correct 23 ms 176216 KB Output is correct
12 Correct 23 ms 176216 KB Output is correct
13 Correct 21 ms 176052 KB Output is correct
14 Correct 23 ms 176220 KB Output is correct
15 Correct 23 ms 176220 KB Output is correct
16 Correct 23 ms 176272 KB Output is correct
17 Correct 24 ms 176220 KB Output is correct
18 Correct 24 ms 176212 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 176208 KB Output is correct
2 Correct 22 ms 176220 KB Output is correct
3 Correct 22 ms 176288 KB Output is correct
4 Correct 23 ms 176220 KB Output is correct
5 Correct 24 ms 176060 KB Output is correct
6 Correct 22 ms 176220 KB Output is correct
7 Correct 21 ms 176208 KB Output is correct
8 Correct 23 ms 176220 KB Output is correct
9 Correct 23 ms 176284 KB Output is correct
10 Correct 22 ms 176196 KB Output is correct
11 Correct 23 ms 176216 KB Output is correct
12 Correct 23 ms 176216 KB Output is correct
13 Correct 21 ms 176052 KB Output is correct
14 Correct 23 ms 176220 KB Output is correct
15 Correct 23 ms 176220 KB Output is correct
16 Correct 23 ms 176272 KB Output is correct
17 Correct 24 ms 176220 KB Output is correct
18 Correct 24 ms 176212 KB Output is correct
19 Incorrect 24 ms 176208 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 176208 KB Output is correct
2 Correct 22 ms 176220 KB Output is correct
3 Correct 22 ms 176288 KB Output is correct
4 Correct 23 ms 176220 KB Output is correct
5 Correct 24 ms 176060 KB Output is correct
6 Correct 22 ms 176220 KB Output is correct
7 Correct 21 ms 176208 KB Output is correct
8 Correct 23 ms 176220 KB Output is correct
9 Correct 23 ms 176284 KB Output is correct
10 Correct 22 ms 176196 KB Output is correct
11 Correct 23 ms 176216 KB Output is correct
12 Correct 23 ms 176216 KB Output is correct
13 Correct 21 ms 176052 KB Output is correct
14 Correct 23 ms 176220 KB Output is correct
15 Correct 23 ms 176220 KB Output is correct
16 Correct 23 ms 176272 KB Output is correct
17 Correct 24 ms 176220 KB Output is correct
18 Correct 24 ms 176212 KB Output is correct
19 Incorrect 82 ms 185936 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 176208 KB Output is correct
2 Correct 22 ms 176220 KB Output is correct
3 Correct 22 ms 176288 KB Output is correct
4 Correct 23 ms 176220 KB Output is correct
5 Correct 24 ms 176060 KB Output is correct
6 Correct 22 ms 176220 KB Output is correct
7 Correct 21 ms 176208 KB Output is correct
8 Correct 23 ms 176220 KB Output is correct
9 Correct 23 ms 176284 KB Output is correct
10 Correct 22 ms 176196 KB Output is correct
11 Correct 23 ms 176216 KB Output is correct
12 Correct 23 ms 176216 KB Output is correct
13 Correct 21 ms 176052 KB Output is correct
14 Correct 23 ms 176220 KB Output is correct
15 Correct 23 ms 176220 KB Output is correct
16 Correct 23 ms 176272 KB Output is correct
17 Correct 24 ms 176220 KB Output is correct
18 Correct 24 ms 176212 KB Output is correct
19 Incorrect 24 ms 176208 KB Output isn't correct
20 Halted 0 ms 0 KB -