oj.uz

Submission #1084816

# Submission time Handle Problem Language Result Execution time Memory
1084816 2024-09-07T04:17:42 Z _Masum_Billah Race (IOI11_race) C++17
0 / 100
 8 ms 13200 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 2e5 + 10;
vector<array<ll, 2>> ad[N];
ll mark[N], sz[N], ans = 1e18, k;
array<ll, 2> nodes[N];
int t, tin[N], tout[N], lv[N];
vector<ll> we(N, 1e18);

ll size(ll node, ll par) {
    sz[node] = 1;
    for (auto [v, w] : ad[node]) {
        if (v != par and !mark[v]) {
            sz[node] += size(v, node);
        }
    }
    return sz[node];
}

ll centroid(ll node, ll par, ll s) {
    for (auto [v, w] : ad[node]) {
        if (v != par and !mark[v]) {
            if (sz[v] > s / 2) return centroid(v, node, s);
        }
    }
    return node;
}
void dfs(ll node, ll par, ll wt, int l = 0) {
    nodes[t] = {node, wt};
    tin[node] = t++;
    lv[node] = l;
    for (auto [v, w] : ad[node]) {
        if (v != par and !mark[v]) {
            dfs(v, node, wt + w, l + 1);
        }
    }
    tout[node] = t - 1;
}

void go(ll node) {
    ll s = size(node, node);
    ll c = centroid(node, node, s);
    mark[c] = 1;
    t = 0;
    dfs(c, c, 0);
    we[0] = 0;
    for (auto [v, w] : ad[c]) {
        if (!mark[v]) {
            for (ll i = tin[v]; i <= tout[v]; i++) {
                auto [a, b] = nodes[i];
                if (k - b >= 0)
                    ans = min(ans, we[k - b] + lv[a]);
            }
            for (ll i = tin[v]; i <= tout[v]; i++) {
                auto [a, b] = nodes[i];
                we[b] = min(we[b], 1ll * lv[a]);
            }
        }
    }
    for (int i = 0; i < t; i++) {
        auto [a, b] = nodes[i];
        we[b] = 1e18;
    }

    for (auto [v, w] : ad[c]) {
        if (!mark[v]) {
            go(v);
        }
    }
}

int best_path(int n, int d, int H[][2], int dis[]) {
    k = d;
    for (int i = 0; i + 1 < n; i++) {
        ad[H[i][0]].push_back({H[i][1], dis[i]});
        ad[H[i][1]].push_back({H[i][0], dis[i]});
    }
    go(0);
    if (ans == 1e18) ans = -1;
    return ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Runtime error 8 ms 13200 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Runtime error 8 ms 13200 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Runtime error 8 ms 13200 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Runtime error 8 ms 13200 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -