oj.uz

Submission #763383

# Submission time Handle Problem Language Result Execution time Memory
763383 2023-06-22T08:54:47 Z boris_mihov Race (IOI11_race) C++17
100 / 100
 398 ms 42888 KB 
#include "race.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 200000 + 10;
const int MAXNUM = 1000000 + 10;
const int INF  = 1e9;

int n, k;
int sz[MAXN];
bool vis[MAXN];
int level[MAXN];
int cnt[MAXNUM];
std::vector <std::pair <int,int>> g[MAXN];
std::vector <int> decomp[MAXN];

void calcSize(int node, int par)
{
    sz[node] = 1;
    for (const auto &[u, cost] : g[node])
    {
        if (u == par || vis[u])
        {
            continue;
        }

        calcSize(u, node);
        sz[node] += sz[u];
    }
}

int findCentroid(int node, int par, int size)
{
    for (const auto &[u, cost] : g[node])
    {
        if (u == par || vis[u])
        {
            continue;
        }

        if (sz[u] > size / 2)
        {
            return findCentroid(u, node, size);
        }
    }

    return node;
}

int decompose(int node, int par)
{
    calcSize(node, 0);
    int cntr = findCentroid(node, par, sz[node]);
    decomp[par].push_back(cntr);
    level[cntr] = level[par] + 1;
    vis[cntr] = true;

    for (const auto &[u, cost] : g[cntr])
    {
        if (vis[u])
        {
            continue;
        }

        decompose(u, cntr);
    }

    return cntr;
}

int updateDFS(int node, int par, int sum, int lvl)
{
    if (sum > k)
    {
        return INF;
    }

    int res = cnt[k - sum];
    for (const auto &[u, cost] : g[node])
    {
        if (level[u] <= lvl || u == par)
        {
            continue;
        }

        res = std::min(res, updateDFS(u, node, sum + cost, lvl) + 1);
    }
    
    return res;
}

void addDFS(int node, int par, int sum, int edges, int lvl)
{
    if (sum > k)
    {
        return;
    }

    cnt[sum] = std::min(cnt[sum], edges);
    for (const auto &[u, cost] : g[node])
    {
        if (level[u] <= lvl || u == par)
        {
            continue;
        }

        addDFS(u, node, sum + cost, edges + 1, lvl);
    }
}

void clearDFS(int node, int par, int sum, int edges, int lvl)
{
    if (sum > k)
    {
        return;
    }

    cnt[sum] = INF;
    for (const auto &[u, cost] : g[node])
    {
        if (level[u] <= lvl || u == par)
        {
            continue;
        }

        clearDFS(u, node, sum + cost, edges + 1, lvl);
    }
}

int rec(int node)
{
    int ans = INF;
    for (const int &u : decomp[node])
    {
        ans = std::min(ans, rec(u));
    }

    cnt[0] = 0;
    for (const auto &[u, cost] : g[node])
    {
        if (level[u] > level[node])
        {
            ans = std::min(ans, 1 + updateDFS(u, node, cost, level[node]));
            addDFS(u, node, cost, 1, level[node]);
        }
    }

    for (const auto &[u, cost] : g[node])
    {
        if (level[u] > level[node])
        {
            clearDFS(u, node, cost, 1, level[node]);
        }
    }


    return ans;
}

int best_path(int N, int K, int H[][2], int L[])
{
    n = N;
    k = K;
    std::fill(cnt + 1, cnt + 1 + k, INF);
    for (int i = 0 ; i < n - 1 ; ++i)
    {
        g[H[i][0] + 1].push_back({H[i][1] + 1, L[i]});
        g[H[i][1] + 1].push_back({H[i][0] + 1, L[i]});
    }

    int root = decompose(1, 0);
    int res = rec(root);
    
    if (res == INF) return -1;
    return res;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9704 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9716 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9708 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 6 ms 9736 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9704 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9716 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9708 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 6 ms 9736 KB Output is correct
19 Correct 5 ms 9720 KB Output is correct
20 Correct 6 ms 9684 KB Output is correct
21 Correct 5 ms 9812 KB Output is correct
22 Correct 7 ms 13308 KB Output is correct
23 Correct 7 ms 12772 KB Output is correct
24 Correct 7 ms 13140 KB Output is correct
25 Correct 8 ms 13012 KB Output is correct
26 Correct 6 ms 11024 KB Output is correct
27 Correct 7 ms 12884 KB Output is correct
28 Correct 6 ms 10580 KB Output is correct
29 Correct 6 ms 11000 KB Output is correct
30 Correct 6 ms 11260 KB Output is correct
31 Correct 7 ms 12372 KB Output is correct
32 Correct 7 ms 12500 KB Output is correct
33 Correct 7 ms 12756 KB Output is correct
34 Correct 6 ms 12116 KB Output is correct
35 Correct 7 ms 12884 KB Output is correct
36 Correct 7 ms 13396 KB Output is correct
37 Correct 7 ms 12868 KB Output is correct
38 Correct 7 ms 11760 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9704 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9716 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9708 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 6 ms 9736 KB Output is correct
19 Correct 113 ms 18200 KB Output is correct
20 Correct 105 ms 18236 KB Output is correct
21 Correct 119 ms 18272 KB Output is correct
22 Correct 108 ms 18288 KB Output is correct
23 Correct 84 ms 18672 KB Output is correct
24 Correct 51 ms 17720 KB Output is correct
25 Correct 112 ms 21600 KB Output is correct
26 Correct 85 ms 24524 KB Output is correct
27 Correct 127 ms 26684 KB Output is correct
28 Correct 215 ms 39600 KB Output is correct
29 Correct 208 ms 38820 KB Output is correct
30 Correct 127 ms 26700 KB Output is correct
31 Correct 136 ms 26624 KB Output is correct
32 Correct 163 ms 26840 KB Output is correct
33 Correct 189 ms 26572 KB Output is correct
34 Correct 169 ms 27548 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9704 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9716 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9708 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 6 ms 9736 KB Output is correct
19 Correct 5 ms 9720 KB Output is correct
20 Correct 6 ms 9684 KB Output is correct
21 Correct 5 ms 9812 KB Output is correct
22 Correct 7 ms 13308 KB Output is correct
23 Correct 7 ms 12772 KB Output is correct
24 Correct 7 ms 13140 KB Output is correct
25 Correct 8 ms 13012 KB Output is correct
26 Correct 6 ms 11024 KB Output is correct
27 Correct 7 ms 12884 KB Output is correct
28 Correct 6 ms 10580 KB Output is correct
29 Correct 6 ms 11000 KB Output is correct
30 Correct 6 ms 11260 KB Output is correct
31 Correct 7 ms 12372 KB Output is correct
32 Correct 7 ms 12500 KB Output is correct
33 Correct 7 ms 12756 KB Output is correct
34 Correct 6 ms 12116 KB Output is correct
35 Correct 7 ms 12884 KB Output is correct
36 Correct 7 ms 13396 KB Output is correct
37 Correct 7 ms 12868 KB Output is correct
38 Correct 7 ms 11760 KB Output is correct
39 Correct 113 ms 18200 KB Output is correct
40 Correct 105 ms 18236 KB Output is correct
41 Correct 119 ms 18272 KB Output is correct
42 Correct 108 ms 18288 KB Output is correct
43 Correct 84 ms 18672 KB Output is correct
44 Correct 51 ms 17720 KB Output is correct
45 Correct 112 ms 21600 KB Output is correct
46 Correct 85 ms 24524 KB Output is correct
47 Correct 127 ms 26684 KB Output is correct
48 Correct 215 ms 39600 KB Output is correct
49 Correct 208 ms 38820 KB Output is correct
50 Correct 127 ms 26700 KB Output is correct
51 Correct 136 ms 26624 KB Output is correct
52 Correct 163 ms 26840 KB Output is correct
53 Correct 189 ms 26572 KB Output is correct
54 Correct 169 ms 27548 KB Output is correct
55 Correct 12 ms 10580 KB Output is correct
56 Correct 15 ms 10528 KB Output is correct
57 Correct 66 ms 18584 KB Output is correct
58 Correct 32 ms 17588 KB Output is correct
59 Correct 89 ms 25184 KB Output is correct
60 Correct 393 ms 42888 KB Output is correct
61 Correct 142 ms 27032 KB Output is correct
62 Correct 149 ms 30668 KB Output is correct
63 Correct 225 ms 30744 KB Output is correct
64 Correct 398 ms 29552 KB Output is correct
65 Correct 170 ms 27904 KB Output is correct
66 Correct 307 ms 40740 KB Output is correct
67 Correct 85 ms 30612 KB Output is correct
68 Correct 203 ms 30924 KB Output is correct
69 Correct 200 ms 31044 KB Output is correct
70 Correct 196 ms 30476 KB Output is correct