oj.uz

Submission #1055389

# Submission time Handle Problem Language Result Execution time Memory
1055389 2024-08-12T18:38:17 Z E_rK Race (IOI11_race) C++14
9 / 100
 82 ms 33360 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[MAXN];
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 2 ms 21592 KB Output is correct
2 Correct 3 ms 21340 KB Output is correct
3 Correct 2 ms 21340 KB Output is correct
4 Correct 2 ms 21340 KB Output is correct
5 Correct 2 ms 21340 KB Output is correct
6 Correct 2 ms 21340 KB Output is correct
7 Correct 3 ms 21336 KB Output is correct
8 Correct 3 ms 21396 KB Output is correct
9 Correct 3 ms 21192 KB Output is correct
10 Correct 2 ms 21400 KB Output is correct
11 Correct 3 ms 21340 KB Output is correct
12 Correct 2 ms 21340 KB Output is correct
13 Correct 4 ms 21340 KB Output is correct
14 Correct 3 ms 21340 KB Output is correct
15 Correct 3 ms 21340 KB Output is correct
16 Correct 3 ms 21340 KB Output is correct
17 Correct 2 ms 21380 KB Output is correct
18 Correct 3 ms 21340 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 21592 KB Output is correct
2 Correct 3 ms 21340 KB Output is correct
3 Correct 2 ms 21340 KB Output is correct
4 Correct 2 ms 21340 KB Output is correct
5 Correct 2 ms 21340 KB Output is correct
6 Correct 2 ms 21340 KB Output is correct
7 Correct 3 ms 21336 KB Output is correct
8 Correct 3 ms 21396 KB Output is correct
9 Correct 3 ms 21192 KB Output is correct
10 Correct 2 ms 21400 KB Output is correct
11 Correct 3 ms 21340 KB Output is correct
12 Correct 2 ms 21340 KB Output is correct
13 Correct 4 ms 21340 KB Output is correct
14 Correct 3 ms 21340 KB Output is correct
15 Correct 3 ms 21340 KB Output is correct
16 Correct 3 ms 21340 KB Output is correct
17 Correct 2 ms 21380 KB Output is correct
18 Correct 3 ms 21340 KB Output is correct
19 Correct 4 ms 21340 KB Output is correct
20 Correct 2 ms 21340 KB Output is correct
21 Correct 3 ms 21336 KB Output is correct
22 Incorrect 3 ms 22952 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 21592 KB Output is correct
2 Correct 3 ms 21340 KB Output is correct
3 Correct 2 ms 21340 KB Output is correct
4 Correct 2 ms 21340 KB Output is correct
5 Correct 2 ms 21340 KB Output is correct
6 Correct 2 ms 21340 KB Output is correct
7 Correct 3 ms 21336 KB Output is correct
8 Correct 3 ms 21396 KB Output is correct
9 Correct 3 ms 21192 KB Output is correct
10 Correct 2 ms 21400 KB Output is correct
11 Correct 3 ms 21340 KB Output is correct
12 Correct 2 ms 21340 KB Output is correct
13 Correct 4 ms 21340 KB Output is correct
14 Correct 3 ms 21340 KB Output is correct
15 Correct 3 ms 21340 KB Output is correct
16 Correct 3 ms 21340 KB Output is correct
17 Correct 2 ms 21380 KB Output is correct
18 Correct 3 ms 21340 KB Output is correct
19 Correct 73 ms 32852 KB Output is correct
20 Correct 69 ms 32820 KB Output is correct
21 Correct 82 ms 32908 KB Output is correct
22 Correct 70 ms 32852 KB Output is correct
23 Incorrect 48 ms 33360 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 21592 KB Output is correct
2 Correct 3 ms 21340 KB Output is correct
3 Correct 2 ms 21340 KB Output is correct
4 Correct 2 ms 21340 KB Output is correct
5 Correct 2 ms 21340 KB Output is correct
6 Correct 2 ms 21340 KB Output is correct
7 Correct 3 ms 21336 KB Output is correct
8 Correct 3 ms 21396 KB Output is correct
9 Correct 3 ms 21192 KB Output is correct
10 Correct 2 ms 21400 KB Output is correct
11 Correct 3 ms 21340 KB Output is correct
12 Correct 2 ms 21340 KB Output is correct
13 Correct 4 ms 21340 KB Output is correct
14 Correct 3 ms 21340 KB Output is correct
15 Correct 3 ms 21340 KB Output is correct
16 Correct 3 ms 21340 KB Output is correct
17 Correct 2 ms 21380 KB Output is correct
18 Correct 3 ms 21340 KB Output is correct
19 Correct 4 ms 21340 KB Output is correct
20 Correct 2 ms 21340 KB Output is correct
21 Correct 3 ms 21336 KB Output is correct
22 Incorrect 3 ms 22952 KB Output isn't correct
23 Halted 0 ms 0 KB -