oj.uz

Submission #532179

# Submission time Handle Problem Language Result Execution time Memory
532179 2022-03-02T09:14:24 Z KiriLL1ca Race (IOI11_race) C++17
100 / 100
 398 ms 83264 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define endl '\n'
#define pb push_back
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define pw(x) (1ll << x)

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;

template <typename T> bool umax (T &a, const T &b) { return (a < b ? a = b, 1 : 0); }
template <typename T> bool umin (T &a, const T &b) { return (a > b ? a = b, 1 : 0); }

template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2e5 + 100;

vector <pii> g[N];
ll deep[N], siz[N], mx[N], sum[N];
set <pii> *sub[N];
/// {sum edges from root, deep}

void calc (int v, int p, int dep, ll depp) {
    siz[v] = 1; mx[v] = -1;
    deep[v] = dep; sum[v] = depp;
    for (auto [u, w] : g[v]) {
        if (u != p) {
            calc(u, v, dep + 1, depp + w);
            siz[v] += siz[u];
            if (mx[v] == -1 || siz[u] > siz[mx[v]]) mx[v] = u;
        }
    }
}

ll ans = 1e18;

void dfs (int v, int p, int k) {
    for (auto [u, w] : g[v]) {
        if (u != p && u != mx[v]) dfs(u, v, k);
    }
    if (mx[v] == -1) {
        sub[v] = new set <pii> ();
    }
    else {
        dfs(mx[v], v, k);
        sub[v] = sub[mx[v]];
    }
    sub[v]->insert({sum[v], deep[v]});
    for (auto [u, w] : g[v]) {
        if (u != p && u != mx[v]) {
            for (auto [sumU, deepU] : *sub[u]) {
                if (sumU - sum[v] > k) continue;
                auto it = (*sub[v]).lower_bound({k + sum[v] - (sumU - sum[v]), -2e9});
                if (it != (*sub[v]).end() && it->fr - sum[v] + sumU - sum[v] == k) ans = min(ans, deepU - deep[v] + it->sc - deep[v]);
            }
            for (auto i : *sub[u]) {
                sub[v]->insert(i);
            }
        }
    }
    /// vertical
    auto it = (*sub[v]).lower_bound({k + sum[v], -2e9});
    if (it != (*sub[v]).end() && it->fr - sum[v] == k) ans = min(ans, it->sc - deep[v]);
}

int best_path (int n, int k, int h[][2], int l[]) {
    for (int i = 0; i < n - 1; ++i) {
        g[h[i][0]].pb({h[i][1], l[i]});
        g[h[i][1]].pb({h[i][0], l[i]});
    }
    calc(0, -1, 0, 0);
    dfs(0, -1, k);
    if (ans == 1e18) ans = -1;
    return ans;
}

//signed main()
//{
//    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    int n, k; cin >> n >> k;
//    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);
//    return 0;
//}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4988 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5000 KB Output is correct
6 Correct 3 ms 5060 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 3 ms 5068 KB Output is correct
9 Correct 3 ms 4996 KB Output is correct
10 Correct 3 ms 5004 KB Output is correct
11 Correct 3 ms 5000 KB Output is correct
12 Correct 3 ms 5068 KB Output is correct
13 Correct 3 ms 4992 KB Output is correct
14 Correct 4 ms 4996 KB Output is correct
15 Correct 3 ms 4996 KB Output is correct
16 Correct 3 ms 5068 KB Output is correct
17 Correct 3 ms 5068 KB Output is correct
18 Correct 3 ms 5068 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4988 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5000 KB Output is correct
6 Correct 3 ms 5060 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 3 ms 5068 KB Output is correct
9 Correct 3 ms 4996 KB Output is correct
10 Correct 3 ms 5004 KB Output is correct
11 Correct 3 ms 5000 KB Output is correct
12 Correct 3 ms 5068 KB Output is correct
13 Correct 3 ms 4992 KB Output is correct
14 Correct 4 ms 4996 KB Output is correct
15 Correct 3 ms 4996 KB Output is correct
16 Correct 3 ms 5068 KB Output is correct
17 Correct 3 ms 5068 KB Output is correct
18 Correct 3 ms 5068 KB Output is correct
19 Correct 4 ms 4996 KB Output is correct
20 Correct 3 ms 5068 KB Output is correct
21 Correct 4 ms 5240 KB Output is correct
22 Correct 5 ms 5328 KB Output is correct
23 Correct 3 ms 5268 KB Output is correct
24 Correct 5 ms 5268 KB Output is correct
25 Correct 4 ms 5324 KB Output is correct
26 Correct 4 ms 5324 KB Output is correct
27 Correct 4 ms 5196 KB Output is correct
28 Correct 4 ms 5196 KB Output is correct
29 Correct 4 ms 5196 KB Output is correct
30 Correct 4 ms 5260 KB Output is correct
31 Correct 4 ms 5196 KB Output is correct
32 Correct 4 ms 5196 KB Output is correct
33 Correct 4 ms 5324 KB Output is correct
34 Correct 3 ms 5196 KB Output is correct
35 Correct 4 ms 5132 KB Output is correct
36 Correct 4 ms 5136 KB Output is correct
37 Correct 3 ms 5196 KB Output is correct
38 Correct 3 ms 5196 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4988 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5000 KB Output is correct
6 Correct 3 ms 5060 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 3 ms 5068 KB Output is correct
9 Correct 3 ms 4996 KB Output is correct
10 Correct 3 ms 5004 KB Output is correct
11 Correct 3 ms 5000 KB Output is correct
12 Correct 3 ms 5068 KB Output is correct
13 Correct 3 ms 4992 KB Output is correct
14 Correct 4 ms 4996 KB Output is correct
15 Correct 3 ms 4996 KB Output is correct
16 Correct 3 ms 5068 KB Output is correct
17 Correct 3 ms 5068 KB Output is correct
18 Correct 3 ms 5068 KB Output is correct
19 Correct 116 ms 29576 KB Output is correct
20 Correct 135 ms 29592 KB Output is correct
21 Correct 128 ms 29312 KB Output is correct
22 Correct 119 ms 29128 KB Output is correct
23 Correct 136 ms 40812 KB Output is correct
24 Correct 113 ms 34416 KB Output is correct
25 Correct 97 ms 29684 KB Output is correct
26 Correct 72 ms 34816 KB Output is correct
27 Correct 188 ms 43836 KB Output is correct
28 Correct 218 ms 65044 KB Output is correct
29 Correct 220 ms 63428 KB Output is correct
30 Correct 194 ms 43744 KB Output is correct
31 Correct 183 ms 43740 KB Output is correct
32 Correct 231 ms 43852 KB Output is correct
33 Correct 175 ms 34172 KB Output is correct
34 Correct 259 ms 58972 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4988 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5000 KB Output is correct
6 Correct 3 ms 5060 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 3 ms 5068 KB Output is correct
9 Correct 3 ms 4996 KB Output is correct
10 Correct 3 ms 5004 KB Output is correct
11 Correct 3 ms 5000 KB Output is correct
12 Correct 3 ms 5068 KB Output is correct
13 Correct 3 ms 4992 KB Output is correct
14 Correct 4 ms 4996 KB Output is correct
15 Correct 3 ms 4996 KB Output is correct
16 Correct 3 ms 5068 KB Output is correct
17 Correct 3 ms 5068 KB Output is correct
18 Correct 3 ms 5068 KB Output is correct
19 Correct 4 ms 4996 KB Output is correct
20 Correct 3 ms 5068 KB Output is correct
21 Correct 4 ms 5240 KB Output is correct
22 Correct 5 ms 5328 KB Output is correct
23 Correct 3 ms 5268 KB Output is correct
24 Correct 5 ms 5268 KB Output is correct
25 Correct 4 ms 5324 KB Output is correct
26 Correct 4 ms 5324 KB Output is correct
27 Correct 4 ms 5196 KB Output is correct
28 Correct 4 ms 5196 KB Output is correct
29 Correct 4 ms 5196 KB Output is correct
30 Correct 4 ms 5260 KB Output is correct
31 Correct 4 ms 5196 KB Output is correct
32 Correct 4 ms 5196 KB Output is correct
33 Correct 4 ms 5324 KB Output is correct
34 Correct 3 ms 5196 KB Output is correct
35 Correct 4 ms 5132 KB Output is correct
36 Correct 4 ms 5136 KB Output is correct
37 Correct 3 ms 5196 KB Output is correct
38 Correct 3 ms 5196 KB Output is correct
39 Correct 116 ms 29576 KB Output is correct
40 Correct 135 ms 29592 KB Output is correct
41 Correct 128 ms 29312 KB Output is correct
42 Correct 119 ms 29128 KB Output is correct
43 Correct 136 ms 40812 KB Output is correct
44 Correct 113 ms 34416 KB Output is correct
45 Correct 97 ms 29684 KB Output is correct
46 Correct 72 ms 34816 KB Output is correct
47 Correct 188 ms 43836 KB Output is correct
48 Correct 218 ms 65044 KB Output is correct
49 Correct 220 ms 63428 KB Output is correct
50 Correct 194 ms 43744 KB Output is correct
51 Correct 183 ms 43740 KB Output is correct
52 Correct 231 ms 43852 KB Output is correct
53 Correct 175 ms 34172 KB Output is correct
54 Correct 259 ms 58972 KB Output is correct
55 Correct 13 ms 8080 KB Output is correct
56 Correct 10 ms 7076 KB Output is correct
57 Correct 66 ms 27524 KB Output is correct
58 Correct 50 ms 25980 KB Output is correct
59 Correct 71 ms 34828 KB Output is correct
60 Correct 209 ms 63908 KB Output is correct
61 Correct 264 ms 48176 KB Output is correct
62 Correct 171 ms 43880 KB Output is correct
63 Correct 219 ms 43892 KB Output is correct
64 Correct 362 ms 83264 KB Output is correct
65 Correct 398 ms 80264 KB Output is correct
66 Correct 242 ms 60096 KB Output is correct
67 Correct 191 ms 48112 KB Output is correct
68 Correct 275 ms 58760 KB Output is correct
69 Correct 321 ms 59596 KB Output is correct
70 Correct 259 ms 56520 KB Output is correct