oj.uz

Submission #881025

# Submission time Handle Problem Language Result Execution time Memory
881025 2023-11-30T11:09:09 Z minhi1 Race (IOI11_race) C++14
100 / 100
 326 ms 59668 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 6;

int n, res = (int)1e9;
long long target;
int sz[N];
int mp[N];
bool is_removed[N];
bool in_map[N];
vector < int > del;
vector < pair < int , int > > adj[N];

int dfs_sz(int u, int p = -1) {
    sz[u] = 1;
    for (auto [v, w] : adj[u]) {
        if (v == p || is_removed[v]) continue;
        sz[u] += dfs_sz(v, u);
    }
    return sz[u];
}

int get_cent(int u, int tree_size, int p) {
    for (auto [v, w] : adj[u]) {
        if (v == p || is_removed[v]) continue;
        if (sz[v] * 2 > tree_size) return get_cent(v, tree_size, u);
    }
    return u;
}

void solve(int u, int cent, int p, long long sum, int dist) {
    if (sum <= target && mp[target - sum] > 0)
        res = min(res, dist + mp[target - sum]);
    if (sum == target) res = min(res, dist);

    for (auto [v, w] : adj[u]) {
        if (v == p || is_removed[v]) continue;
        if (sum + w > target) continue;
        solve(v, cent, u, sum + w, dist + 1);
    }
}

void upd(int u, int cent, int p, long long sum, int dist) {
    if (sum <= target) {
        int val = mp[sum];
        val = min(val, dist);
        mp[sum] = val;
        if (!in_map[sum]) {
            in_map[sum] = true;
            del.push_back(sum);
        }
    }

    for (auto [v, w] : adj[u]) {
        if (v == p || is_removed[v]) continue;
        if (sum + w > target) continue;
        upd(v, cent, u, sum + w, dist + 1);
    }
}

void decomp(int u) {
    int cent = get_cent(u, dfs_sz(u), -1);

    mp[0] = 0;
    for (auto [v, w] : adj[cent]) {
        if (is_removed[v]) continue;
        solve(v, cent, cent, w, 1);
        upd(v, cent, cent, w, 1);
    }

    // TODO: refresh
    for (int sum : del) {
        mp[sum] = (int)1e9;
        in_map[sum] = 0;
    }
    del.clear();

    is_removed[cent] = true;

    for (auto [v, w] : adj[cent]) {
        if (is_removed[v]) continue;
        decomp(v);
    }
}

int best_path(int n, int k, int h[][2], int l[]) {
    n = n;
    target = k;
    del.clear();
    for (int i = 1; i < N; ++i) mp[i] = (int)1e9;
    for (int i = 0; i < n - 1; ++i) {
        int u = h[i][0], v = h[i][1], w = l[i];
        ++u; ++v;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    decomp(1);

    return (res == (int)1e9 ? -1 : res);
}

//int main() {
//    ios::sync_with_stdio(0);
//    cin.tie(0);
//
//    #ifdef trcute
//        freopen("test.inp", "r", stdin);
//        // freopen("test.out", "w", stdout);
//    #endif
//
//    cin >> n >> target;
//    for (int i = 1; i < n; ++i) {
//        int u, v, w;
//        cin >> u >> v >> w;
//        ++u; ++v;
//        adj[u].push_back({v, w});
//        adj[v].push_back({u, w});
//    }
//
//    decomp(1);
//
//    cout << (res == (int)1e9 ? -1 : res);
//
//    return 0;
//}

Compilation message

race.cpp: In function 'int dfs_sz(int, int)':
race.cpp:17:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for (auto [v, w] : adj[u]) {
      |               ^
race.cpp: In function 'int get_cent(int, int, int)':
race.cpp:25:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |     for (auto [v, w] : adj[u]) {
      |               ^
race.cpp: In function 'void solve(int, int, int, long long int, int)':
race.cpp:37:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |     for (auto [v, w] : adj[u]) {
      |               ^
race.cpp: In function 'void upd(int, int, int, long long int, int)':
race.cpp:55:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for (auto [v, w] : adj[u]) {
      |               ^
race.cpp: In function 'void decomp(int)':
race.cpp:66:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |     for (auto [v, w] : adj[cent]) {
      |               ^
race.cpp:81:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |     for (auto [v, w] : adj[cent]) {
      |               ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 35164 KB Output is correct
2 Correct 7 ms 35164 KB Output is correct
3 Correct 8 ms 35164 KB Output is correct
4 Correct 8 ms 35164 KB Output is correct
5 Correct 8 ms 35164 KB Output is correct
6 Correct 8 ms 35292 KB Output is correct
7 Correct 8 ms 35164 KB Output is correct
8 Correct 8 ms 35164 KB Output is correct
9 Correct 7 ms 35332 KB Output is correct
10 Correct 7 ms 35252 KB Output is correct
11 Correct 7 ms 35164 KB Output is correct
12 Correct 8 ms 35420 KB Output is correct
13 Correct 7 ms 35164 KB Output is correct
14 Correct 7 ms 35308 KB Output is correct
15 Correct 7 ms 35160 KB Output is correct
16 Correct 7 ms 35160 KB Output is correct
17 Correct 8 ms 35164 KB Output is correct
18 Correct 7 ms 35164 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 35164 KB Output is correct
2 Correct 7 ms 35164 KB Output is correct
3 Correct 8 ms 35164 KB Output is correct
4 Correct 8 ms 35164 KB Output is correct
5 Correct 8 ms 35164 KB Output is correct
6 Correct 8 ms 35292 KB Output is correct
7 Correct 8 ms 35164 KB Output is correct
8 Correct 8 ms 35164 KB Output is correct
9 Correct 7 ms 35332 KB Output is correct
10 Correct 7 ms 35252 KB Output is correct
11 Correct 7 ms 35164 KB Output is correct
12 Correct 8 ms 35420 KB Output is correct
13 Correct 7 ms 35164 KB Output is correct
14 Correct 7 ms 35308 KB Output is correct
15 Correct 7 ms 35160 KB Output is correct
16 Correct 7 ms 35160 KB Output is correct
17 Correct 8 ms 35164 KB Output is correct
18 Correct 7 ms 35164 KB Output is correct
19 Correct 7 ms 35296 KB Output is correct
20 Correct 8 ms 35300 KB Output is correct
21 Correct 7 ms 35164 KB Output is correct
22 Correct 8 ms 35164 KB Output is correct
23 Correct 9 ms 35336 KB Output is correct
24 Correct 7 ms 35164 KB Output is correct
25 Correct 7 ms 35320 KB Output is correct
26 Correct 9 ms 35368 KB Output is correct
27 Correct 8 ms 35324 KB Output is correct
28 Correct 9 ms 35164 KB Output is correct
29 Correct 8 ms 35164 KB Output is correct
30 Correct 8 ms 35248 KB Output is correct
31 Correct 8 ms 35164 KB Output is correct
32 Correct 8 ms 35272 KB Output is correct
33 Correct 8 ms 35284 KB Output is correct
34 Correct 7 ms 35164 KB Output is correct
35 Correct 8 ms 35316 KB Output is correct
36 Correct 7 ms 35164 KB Output is correct
37 Correct 9 ms 35164 KB Output is correct
38 Correct 8 ms 35164 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 35164 KB Output is correct
2 Correct 7 ms 35164 KB Output is correct
3 Correct 8 ms 35164 KB Output is correct
4 Correct 8 ms 35164 KB Output is correct
5 Correct 8 ms 35164 KB Output is correct
6 Correct 8 ms 35292 KB Output is correct
7 Correct 8 ms 35164 KB Output is correct
8 Correct 8 ms 35164 KB Output is correct
9 Correct 7 ms 35332 KB Output is correct
10 Correct 7 ms 35252 KB Output is correct
11 Correct 7 ms 35164 KB Output is correct
12 Correct 8 ms 35420 KB Output is correct
13 Correct 7 ms 35164 KB Output is correct
14 Correct 7 ms 35308 KB Output is correct
15 Correct 7 ms 35160 KB Output is correct
16 Correct 7 ms 35160 KB Output is correct
17 Correct 8 ms 35164 KB Output is correct
18 Correct 7 ms 35164 KB Output is correct
19 Correct 89 ms 42448 KB Output is correct
20 Correct 92 ms 42536 KB Output is correct
21 Correct 92 ms 42568 KB Output is correct
22 Correct 83 ms 42660 KB Output is correct
23 Correct 54 ms 42832 KB Output is correct
24 Correct 45 ms 42576 KB Output is correct
25 Correct 93 ms 45136 KB Output is correct
26 Correct 72 ms 48260 KB Output is correct
27 Correct 115 ms 47868 KB Output is correct
28 Correct 157 ms 59132 KB Output is correct
29 Correct 158 ms 58452 KB Output is correct
30 Correct 107 ms 47848 KB Output is correct
31 Correct 122 ms 47956 KB Output is correct
32 Correct 121 ms 47952 KB Output is correct
33 Correct 133 ms 47104 KB Output is correct
34 Correct 141 ms 47696 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 35164 KB Output is correct
2 Correct 7 ms 35164 KB Output is correct
3 Correct 8 ms 35164 KB Output is correct
4 Correct 8 ms 35164 KB Output is correct
5 Correct 8 ms 35164 KB Output is correct
6 Correct 8 ms 35292 KB Output is correct
7 Correct 8 ms 35164 KB Output is correct
8 Correct 8 ms 35164 KB Output is correct
9 Correct 7 ms 35332 KB Output is correct
10 Correct 7 ms 35252 KB Output is correct
11 Correct 7 ms 35164 KB Output is correct
12 Correct 8 ms 35420 KB Output is correct
13 Correct 7 ms 35164 KB Output is correct
14 Correct 7 ms 35308 KB Output is correct
15 Correct 7 ms 35160 KB Output is correct
16 Correct 7 ms 35160 KB Output is correct
17 Correct 8 ms 35164 KB Output is correct
18 Correct 7 ms 35164 KB Output is correct
19 Correct 7 ms 35296 KB Output is correct
20 Correct 8 ms 35300 KB Output is correct
21 Correct 7 ms 35164 KB Output is correct
22 Correct 8 ms 35164 KB Output is correct
23 Correct 9 ms 35336 KB Output is correct
24 Correct 7 ms 35164 KB Output is correct
25 Correct 7 ms 35320 KB Output is correct
26 Correct 9 ms 35368 KB Output is correct
27 Correct 8 ms 35324 KB Output is correct
28 Correct 9 ms 35164 KB Output is correct
29 Correct 8 ms 35164 KB Output is correct
30 Correct 8 ms 35248 KB Output is correct
31 Correct 8 ms 35164 KB Output is correct
32 Correct 8 ms 35272 KB Output is correct
33 Correct 8 ms 35284 KB Output is correct
34 Correct 7 ms 35164 KB Output is correct
35 Correct 8 ms 35316 KB Output is correct
36 Correct 7 ms 35164 KB Output is correct
37 Correct 9 ms 35164 KB Output is correct
38 Correct 8 ms 35164 KB Output is correct
39 Correct 89 ms 42448 KB Output is correct
40 Correct 92 ms 42536 KB Output is correct
41 Correct 92 ms 42568 KB Output is correct
42 Correct 83 ms 42660 KB Output is correct
43 Correct 54 ms 42832 KB Output is correct
44 Correct 45 ms 42576 KB Output is correct
45 Correct 93 ms 45136 KB Output is correct
46 Correct 72 ms 48260 KB Output is correct
47 Correct 115 ms 47868 KB Output is correct
48 Correct 157 ms 59132 KB Output is correct
49 Correct 158 ms 58452 KB Output is correct
50 Correct 107 ms 47848 KB Output is correct
51 Correct 122 ms 47956 KB Output is correct
52 Correct 121 ms 47952 KB Output is correct
53 Correct 133 ms 47104 KB Output is correct
54 Correct 141 ms 47696 KB Output is correct
55 Correct 16 ms 35672 KB Output is correct
56 Correct 13 ms 35676 KB Output is correct
57 Correct 58 ms 42580 KB Output is correct
58 Correct 32 ms 42448 KB Output is correct
59 Correct 75 ms 48852 KB Output is correct
60 Correct 268 ms 59668 KB Output is correct
61 Correct 122 ms 48212 KB Output is correct
62 Correct 131 ms 48128 KB Output is correct
63 Correct 168 ms 48012 KB Output is correct
64 Correct 326 ms 48960 KB Output is correct
65 Correct 123 ms 49096 KB Output is correct
66 Correct 248 ms 56400 KB Output is correct
67 Correct 72 ms 48580 KB Output is correct
68 Correct 175 ms 49556 KB Output is correct
69 Correct 190 ms 49616 KB Output is correct
70 Correct 161 ms 49112 KB Output is correct