oj.uz

Submission #1082298

# Submission time Handle Problem Language Result Execution time Memory
1082298 2024-08-31T05:50:01 Z thieunguyenhuy Race (IOI11_race) C++17
100 / 100
 216 ms 39604 KB 
#ifndef hwe
    #include "race.h"
#endif

#include <bits/stdc++.h>
using namespace std;

#define popcount(n) (__builtin_popcountll((n)))
#define clz(n) (__builtin_clzll((n)))
#define ctz(n) (__builtin_ctzll((n)))
#define lg(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))

#define Int __int128
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;

template <class T1, class T2>
bool maximize(T1 &x, T2 y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T1, class T2>
bool minimize(T1 &x, T2 y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T>
void remove_duplicate(vector<T> &ve) {
    sort (ve.begin(), ve.end());
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T> T random(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
template <class T> T random(T r) {
    return rng() % r;
}

const int N = 2e5 + 5, K = 1e6 + 5;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;

int n, k, ans = inf;
int sz[N], f[K];
vector<int> all_lengths;
vii adj[N];
bitset<N> deleted;

void count_child(int u, int fa) {
    sz[u] = 1;
    for (auto it : adj[u]) {
        int v = it.fi;
        if (v != fa && !deleted[v]) {
            count_child(v, u);
            sz[u] += sz[v];
        }
    }
}

int get_centroid(const int n, int u, int fa) {
    for (auto it : adj[u]) {
        int v = it.fi;
        if (v != fa && !deleted[v] && 2 * sz[v] > n) return get_centroid(n, v, u);
    }
    return u;
}

void dfs(int u, int fa, int depth, int length, bool update) {
    if (length > k) return;
    if (update) {
        minimize(f[length], depth);
        all_lengths.emplace_back(length);
    }
    else minimize(ans, depth + f[k - length]);
    for (auto it : adj[u]) {
        int v = it.fi, w = it.se;
        if (v != fa && !deleted[v]) dfs(v, u, depth + 1, length + w, update);
    }
}

void centroid_decomp(int u) {
    count_child(u, -1); int centroid = get_centroid(sz[u], u, -1);
    deleted[centroid] = true;

    all_lengths.clear(); f[0] = 0;
    for (auto it : adj[centroid]) {
        int v = it.fi, w = it.se;
        if (!deleted[v]) {
            dfs(v, centroid, 1, w, false);
            dfs(v, centroid, 1, w, true);
        }
    }

    for (auto length : all_lengths) f[length] = inf;

    for (auto it : adj[centroid]) if (!deleted[it.fi]) {
        centroid_decomp(it.fi);
    }
}

int best_path(int _n, int _k, int H[][2], int L[]) {
    n = _n, k = _k;
    for (int i = 0; i < n - 1; ++i) {
        int u = H[i][0], v = H[i][1], w = L[i];
        adj[u].emplace_back(v, w),
        adj[v].emplace_back(u, w);
    }

    for (int i = 0; i <= k; ++i) f[i] = inf;
    ans = inf; centroid_decomp(1);
    return (ans == inf ? -1 : ans);
}

#ifdef hwe
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int n = 11, k = 12;
    int H[n - 1][2], L[n - 1];

    for (int i = 0; i < n - 1; ++i) cin >> H[i][0] >> H[i][1];
    for (int i = 0; i < n - 1; ++i) cin >> L[i];

    cout << best_path(n, k, H, L);

    cerr << '\n'; return 0;
}
#endif

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 2 ms 12632 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12632 KB Output is correct
12 Correct 2 ms 12636 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12632 KB Output is correct
15 Correct 1 ms 12636 KB Output is correct
16 Correct 1 ms 12636 KB Output is correct
17 Correct 2 ms 12632 KB Output is correct
18 Correct 1 ms 12636 KB Output is correct
19 Correct 2 ms 12636 KB Output is correct
20 Correct 2 ms 12636 KB Output is correct
21 Correct 2 ms 12636 KB Output is correct
22 Correct 2 ms 12636 KB Output is correct
23 Correct 2 ms 12636 KB Output is correct
24 Correct 2 ms 12636 KB Output is correct
25 Correct 2 ms 12636 KB Output is correct
26 Correct 2 ms 12636 KB Output is correct
27 Correct 2 ms 12636 KB Output is correct
28 Correct 2 ms 12636 KB Output is correct
29 Correct 2 ms 12636 KB Output is correct
30 Correct 2 ms 12636 KB Output is correct
31 Correct 2 ms 12636 KB Output is correct
32 Correct 2 ms 12636 KB Output is correct
33 Correct 2 ms 12636 KB Output is correct
34 Correct 2 ms 12636 KB Output is correct
35 Correct 2 ms 12636 KB Output is correct
36 Correct 2 ms 12636 KB Output is correct
37 Correct 3 ms 12636 KB Output is correct
38 Correct 2 ms 12636 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 2 ms 12632 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12632 KB Output is correct
12 Correct 2 ms 12636 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12632 KB Output is correct
15 Correct 1 ms 12636 KB Output is correct
16 Correct 1 ms 12636 KB Output is correct
17 Correct 2 ms 12632 KB Output is correct
18 Correct 1 ms 12636 KB Output is correct
19 Correct 76 ms 20316 KB Output is correct
20 Correct 71 ms 20316 KB Output is correct
21 Correct 74 ms 20564 KB Output is correct
22 Correct 70 ms 20944 KB Output is correct
23 Correct 41 ms 20564 KB Output is correct
24 Correct 33 ms 20572 KB Output is correct
25 Correct 75 ms 26884 KB Output is correct
26 Correct 61 ms 28128 KB Output is correct
27 Correct 89 ms 26248 KB Output is correct
28 Correct 135 ms 39604 KB Output is correct
29 Correct 123 ms 34388 KB Output is correct
30 Correct 99 ms 26196 KB Output is correct
31 Correct 86 ms 26244 KB Output is correct
32 Correct 92 ms 26220 KB Output is correct
33 Correct 110 ms 24808 KB Output is correct
34 Correct 97 ms 25748 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 2 ms 12632 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12632 KB Output is correct
12 Correct 2 ms 12636 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12632 KB Output is correct
15 Correct 1 ms 12636 KB Output is correct
16 Correct 1 ms 12636 KB Output is correct
17 Correct 2 ms 12632 KB Output is correct
18 Correct 1 ms 12636 KB Output is correct
19 Correct 2 ms 12636 KB Output is correct
20 Correct 2 ms 12636 KB Output is correct
21 Correct 2 ms 12636 KB Output is correct
22 Correct 2 ms 12636 KB Output is correct
23 Correct 2 ms 12636 KB Output is correct
24 Correct 2 ms 12636 KB Output is correct
25 Correct 2 ms 12636 KB Output is correct
26 Correct 2 ms 12636 KB Output is correct
27 Correct 2 ms 12636 KB Output is correct
28 Correct 2 ms 12636 KB Output is correct
29 Correct 2 ms 12636 KB Output is correct
30 Correct 2 ms 12636 KB Output is correct
31 Correct 2 ms 12636 KB Output is correct
32 Correct 2 ms 12636 KB Output is correct
33 Correct 2 ms 12636 KB Output is correct
34 Correct 2 ms 12636 KB Output is correct
35 Correct 2 ms 12636 KB Output is correct
36 Correct 2 ms 12636 KB Output is correct
37 Correct 3 ms 12636 KB Output is correct
38 Correct 2 ms 12636 KB Output is correct
39 Correct 76 ms 20316 KB Output is correct
40 Correct 71 ms 20316 KB Output is correct
41 Correct 74 ms 20564 KB Output is correct
42 Correct 70 ms 20944 KB Output is correct
43 Correct 41 ms 20564 KB Output is correct
44 Correct 33 ms 20572 KB Output is correct
45 Correct 75 ms 26884 KB Output is correct
46 Correct 61 ms 28128 KB Output is correct
47 Correct 89 ms 26248 KB Output is correct
48 Correct 135 ms 39604 KB Output is correct
49 Correct 123 ms 34388 KB Output is correct
50 Correct 99 ms 26196 KB Output is correct
51 Correct 86 ms 26244 KB Output is correct
52 Correct 92 ms 26220 KB Output is correct
53 Correct 110 ms 24808 KB Output is correct
54 Correct 97 ms 25748 KB Output is correct
55 Correct 8 ms 13144 KB Output is correct
56 Correct 8 ms 13148 KB Output is correct
57 Correct 46 ms 21176 KB Output is correct
58 Correct 27 ms 21176 KB Output is correct
59 Correct 64 ms 28128 KB Output is correct
60 Correct 216 ms 34016 KB Output is correct
61 Correct 95 ms 26608 KB Output is correct
62 Correct 103 ms 27340 KB Output is correct
63 Correct 118 ms 27348 KB Output is correct
64 Correct 190 ms 27592 KB Output is correct
65 Correct 90 ms 26960 KB Output is correct
66 Correct 183 ms 38228 KB Output is correct
67 Correct 62 ms 28612 KB Output is correct
68 Correct 107 ms 27624 KB Output is correct
69 Correct 111 ms 27800 KB Output is correct
70 Correct 112 ms 27076 KB Output is correct