oj.uz

Submission #1055395

# Submission time Handle Problem Language Result Execution time Memory
1055395 2024-08-12T18:40:16 Z E_rK Race (IOI11_race) C++14
21 / 100
 84 ms 33624 KB 
#include <bits/stdc++.h>
#include "race.h"

using namespace std;
#define MAXN 500005
#define pb push_back
#define fi first
#define se second
typedef long long int lo;

lo k;
vector<pair<lo,lo> > v[MAXN];
lo vis[MAXN];
lo sub[MAXN];
lo mpp[1000005];
lo ans;
void dfs(lo node, lo par)
{
    sub[node] = 1;
    for(auto e: v[node]){
        if(e.fi == par or vis[e.fi])
            continue;
        dfs(e.fi,node);
        sub[node] += sub[e.fi];
    }
}

lo centroid(lo node, lo par, lo val){
    for(auto e: v[node]){
        if(e.fi == par or vis[e.fi])
            continue;
        if(sub[e.fi] >= val/2)
            return centroid(e.fi,node,val);
    }
    return node;
}
void check(lo node, lo par, lo cost,lo num){
    if(cost > k)
        return;
    if(mpp[k-cost] != -1)
        ans = min(ans, mpp[k-cost] + num);
    for(auto e: v[node]){
        if(e.fi == par or vis[e.fi])
            continue;
        check(e.fi,node,cost+e.se,num+1);
    }
}
void build(lo node, lo par, lo cost,lo num){
    if(cost > k)
        return;
    if(mpp[cost] == -1)
        mpp[cost] = num;
    else
        mpp[cost] = min(num,mpp[cost]);
    for(auto e: v[node]){
        if(e.fi == par or vis[e.fi])
            continue;
        build(e.fi,node,cost+e.se,num+1);
    }
}

void sifirla(lo node, lo par, lo cost){
    if(cost > k)
        return;
    mpp[cost] = -1;
    for(auto e:v[node]){
        if(e.fi == par || vis[e.fi])continue;
        sifirla(e.fi,node,cost+e.se);
    }
}

void solve(lo node)
{
    dfs(node,-1);
    lo c = centroid(node,-1,sub[node]);
    for(auto e: v[c]){
        if(vis[e.fi])
            continue;
        check(e.fi,c,e.se,1);
        build(e.fi,c,e.se,1);
    }
    for(auto e: v[c]){
        if(vis[e.fi])
            continue;
        sifirla(e.fi,c,e.se);
    }
    vis[c]=1;
    for(auto e: v[c]){
        if(vis[e.fi])
            continue;
        solve(e.fi);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    memset(mpp,-1,sizeof(mpp));
    for (int i = 0; i < N-1; ++i)
    {
        v[H[i][0]].pb({H[i][1],L[i]});
        v[H[i][1]].pb({H[i][0],L[i]});
    }
    ans = N+5;
    solve(0);
    if(ans == N+5)
        ans = -1;
    return ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25176 KB Output is correct
2 Correct 3 ms 25180 KB Output is correct
3 Correct 4 ms 25180 KB Output is correct
4 Correct 3 ms 25280 KB Output is correct
5 Correct 3 ms 25268 KB Output is correct
6 Correct 3 ms 25180 KB Output is correct
7 Correct 3 ms 25180 KB Output is correct
8 Correct 4 ms 25180 KB Output is correct
9 Correct 3 ms 25340 KB Output is correct
10 Correct 3 ms 25180 KB Output is correct
11 Correct 4 ms 25180 KB Output is correct
12 Correct 4 ms 25180 KB Output is correct
13 Correct 3 ms 25180 KB Output is correct
14 Correct 4 ms 25180 KB Output is correct
15 Correct 3 ms 25216 KB Output is correct
16 Correct 3 ms 25284 KB Output is correct
17 Correct 3 ms 25180 KB Output is correct
18 Correct 3 ms 25180 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25176 KB Output is correct
2 Correct 3 ms 25180 KB Output is correct
3 Correct 4 ms 25180 KB Output is correct
4 Correct 3 ms 25280 KB Output is correct
5 Correct 3 ms 25268 KB Output is correct
6 Correct 3 ms 25180 KB Output is correct
7 Correct 3 ms 25180 KB Output is correct
8 Correct 4 ms 25180 KB Output is correct
9 Correct 3 ms 25340 KB Output is correct
10 Correct 3 ms 25180 KB Output is correct
11 Correct 4 ms 25180 KB Output is correct
12 Correct 4 ms 25180 KB Output is correct
13 Correct 3 ms 25180 KB Output is correct
14 Correct 4 ms 25180 KB Output is correct
15 Correct 3 ms 25216 KB Output is correct
16 Correct 3 ms 25284 KB Output is correct
17 Correct 3 ms 25180 KB Output is correct
18 Correct 3 ms 25180 KB Output is correct
19 Correct 4 ms 25316 KB Output is correct
20 Correct 3 ms 25180 KB Output is correct
21 Correct 3 ms 25180 KB Output is correct
22 Correct 3 ms 25180 KB Output is correct
23 Correct 3 ms 25180 KB Output is correct
24 Correct 4 ms 25176 KB Output is correct
25 Correct 3 ms 25180 KB Output is correct
26 Correct 3 ms 25180 KB Output is correct
27 Correct 6 ms 25180 KB Output is correct
28 Correct 3 ms 25408 KB Output is correct
29 Correct 6 ms 25328 KB Output is correct
30 Correct 3 ms 25176 KB Output is correct
31 Correct 5 ms 25180 KB Output is correct
32 Correct 3 ms 25308 KB Output is correct
33 Correct 4 ms 25332 KB Output is correct
34 Correct 5 ms 25180 KB Output is correct
35 Correct 3 ms 25180 KB Output is correct
36 Correct 3 ms 25180 KB Output is correct
37 Correct 3 ms 25180 KB Output is correct
38 Correct 3 ms 25180 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25176 KB Output is correct
2 Correct 3 ms 25180 KB Output is correct
3 Correct 4 ms 25180 KB Output is correct
4 Correct 3 ms 25280 KB Output is correct
5 Correct 3 ms 25268 KB Output is correct
6 Correct 3 ms 25180 KB Output is correct
7 Correct 3 ms 25180 KB Output is correct
8 Correct 4 ms 25180 KB Output is correct
9 Correct 3 ms 25340 KB Output is correct
10 Correct 3 ms 25180 KB Output is correct
11 Correct 4 ms 25180 KB Output is correct
12 Correct 4 ms 25180 KB Output is correct
13 Correct 3 ms 25180 KB Output is correct
14 Correct 4 ms 25180 KB Output is correct
15 Correct 3 ms 25216 KB Output is correct
16 Correct 3 ms 25284 KB Output is correct
17 Correct 3 ms 25180 KB Output is correct
18 Correct 3 ms 25180 KB Output is correct
19 Correct 84 ms 33316 KB Output is correct
20 Correct 67 ms 33180 KB Output is correct
21 Correct 81 ms 33360 KB Output is correct
22 Correct 72 ms 33364 KB Output is correct
23 Incorrect 39 ms 33624 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25176 KB Output is correct
2 Correct 3 ms 25180 KB Output is correct
3 Correct 4 ms 25180 KB Output is correct
4 Correct 3 ms 25280 KB Output is correct
5 Correct 3 ms 25268 KB Output is correct
6 Correct 3 ms 25180 KB Output is correct
7 Correct 3 ms 25180 KB Output is correct
8 Correct 4 ms 25180 KB Output is correct
9 Correct 3 ms 25340 KB Output is correct
10 Correct 3 ms 25180 KB Output is correct
11 Correct 4 ms 25180 KB Output is correct
12 Correct 4 ms 25180 KB Output is correct
13 Correct 3 ms 25180 KB Output is correct
14 Correct 4 ms 25180 KB Output is correct
15 Correct 3 ms 25216 KB Output is correct
16 Correct 3 ms 25284 KB Output is correct
17 Correct 3 ms 25180 KB Output is correct
18 Correct 3 ms 25180 KB Output is correct
19 Correct 4 ms 25316 KB Output is correct
20 Correct 3 ms 25180 KB Output is correct
21 Correct 3 ms 25180 KB Output is correct
22 Correct 3 ms 25180 KB Output is correct
23 Correct 3 ms 25180 KB Output is correct
24 Correct 4 ms 25176 KB Output is correct
25 Correct 3 ms 25180 KB Output is correct
26 Correct 3 ms 25180 KB Output is correct
27 Correct 6 ms 25180 KB Output is correct
28 Correct 3 ms 25408 KB Output is correct
29 Correct 6 ms 25328 KB Output is correct
30 Correct 3 ms 25176 KB Output is correct
31 Correct 5 ms 25180 KB Output is correct
32 Correct 3 ms 25308 KB Output is correct
33 Correct 4 ms 25332 KB Output is correct
34 Correct 5 ms 25180 KB Output is correct
35 Correct 3 ms 25180 KB Output is correct
36 Correct 3 ms 25180 KB Output is correct
37 Correct 3 ms 25180 KB Output is correct
38 Correct 3 ms 25180 KB Output is correct
39 Correct 84 ms 33316 KB Output is correct
40 Correct 67 ms 33180 KB Output is correct
41 Correct 81 ms 33360 KB Output is correct
42 Correct 72 ms 33364 KB Output is correct
43 Incorrect 39 ms 33624 KB Output isn't correct
44 Halted 0 ms 0 KB -