oj.uz

Submission #370606

# Submission time Handle Problem Language Result Execution time Memory
370606 2021-02-24T08:35:41 Z KoD Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 234 ms 15332 KB 
#include <bits/stdc++.h>
#include "railroad.h"

template <class T>
using Vec = std::vector<T>;
using ll = long long;

constexpr int MAX = 1000000000;

struct DSU {
    Vec<int> par;
    DSU(const int n): par(n, -1) { }
    int find(const int u) {
        return par[u] < 0 ? u : par[u] = find(par[u]);
    }
    bool merge(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) {
            return false;
        }
        if (par[u] > par[v]) {
            std::swap(u, v);
        }
        par[u] += par[v];
        par[v] = u;
        return true;
    }
};

ll plan_roller_coaster(Vec<int> s, Vec<int> t) {
    s.push_back(MAX);
    t.push_back(1);
    const int n = (int) s.size();
    Vec<int> cmp;
    cmp.reserve(2 * n);
    std::copy(s.cbegin(), s.cend(), std::back_inserter(cmp));
    std::copy(t.cbegin(), t.cend(), std::back_inserter(cmp));
    std::sort(cmp.begin(), cmp.end());
    cmp.erase(std::unique(cmp.begin(), cmp.end()), cmp.end());
    for (auto &x: s) {
        x = std::lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
    }
    for (auto &x: t) {
        x = std::lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
    }
    const int len = (int) cmp.size();
    Vec<int> coeff(len);
    for (const auto x: s) {
        coeff[x] -= 1;
    }
    for (const auto x: t) {
        coeff[x] += 1;
    }
    int current = 0;
    DSU dsu(len);
    ll ret = 0;
    Vec<std::tuple<int, int, int>> edges;
    for (int i = 0; i < len; ++i) {
        current += coeff[i];
        if (current < 0) {
            ret += (ll) -current * (cmp[i + 1] - cmp[i]);
        }
        if (current != 0) {
            dsu.merge(i, i + 1);
        }
        else if (i + 1 != len) {
            edges.emplace_back(cmp[i + 1] - cmp[i], i, i + 1);
        }
    }
    for (int i = 0; i < n; ++i) {
        dsu.merge(s[i], t[i]);
    }
    std::sort(edges.begin(), edges.end());
    for (const auto [c, u, v]: edges) {
        if (dsu.merge(u, v)) {
            ret += c;
        }
    }
    return ret;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB n = 2
2 Correct 1 ms 364 KB n = 2
3 Correct 1 ms 364 KB n = 2
4 Correct 1 ms 364 KB n = 2
5 Correct 1 ms 364 KB n = 2
6 Correct 1 ms 364 KB n = 2
7 Correct 1 ms 364 KB n = 3
8 Correct 1 ms 364 KB n = 3
9 Correct 1 ms 364 KB n = 3
10 Correct 1 ms 364 KB n = 8
11 Correct 1 ms 364 KB n = 8
12 Correct 1 ms 364 KB n = 8
13 Correct 1 ms 364 KB n = 8
14 Correct 1 ms 364 KB n = 8
15 Correct 1 ms 364 KB n = 8
16 Correct 1 ms 364 KB n = 8
17 Correct 1 ms 364 KB n = 8
18 Correct 1 ms 364 KB n = 8
19 Correct 1 ms 364 KB n = 3
20 Correct 1 ms 364 KB n = 7
21 Correct 1 ms 364 KB n = 8
22 Correct 1 ms 364 KB n = 8
23 Correct 1 ms 364 KB n = 8
24 Correct 1 ms 364 KB n = 8
25 Correct 1 ms 364 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB n = 2
2 Correct 1 ms 364 KB n = 2
3 Correct 1 ms 364 KB n = 2
4 Correct 1 ms 364 KB n = 2
5 Correct 1 ms 364 KB n = 2
6 Correct 1 ms 364 KB n = 2
7 Correct 1 ms 364 KB n = 3
8 Correct 1 ms 364 KB n = 3
9 Correct 1 ms 364 KB n = 3
10 Correct 1 ms 364 KB n = 8
11 Correct 1 ms 364 KB n = 8
12 Correct 1 ms 364 KB n = 8
13 Correct 1 ms 364 KB n = 8
14 Correct 1 ms 364 KB n = 8
15 Correct 1 ms 364 KB n = 8
16 Correct 1 ms 364 KB n = 8
17 Correct 1 ms 364 KB n = 8
18 Correct 1 ms 364 KB n = 8
19 Correct 1 ms 364 KB n = 3
20 Correct 1 ms 364 KB n = 7
21 Correct 1 ms 364 KB n = 8
22 Correct 1 ms 364 KB n = 8
23 Correct 1 ms 364 KB n = 8
24 Correct 1 ms 364 KB n = 8
25 Correct 1 ms 364 KB n = 8
26 Correct 1 ms 364 KB n = 8
27 Correct 1 ms 364 KB n = 8
28 Correct 1 ms 364 KB n = 8
29 Correct 1 ms 364 KB n = 16
30 Correct 1 ms 364 KB n = 16
31 Correct 1 ms 364 KB n = 16
32 Correct 1 ms 364 KB n = 16
33 Correct 1 ms 364 KB n = 16
34 Correct 1 ms 364 KB n = 16
35 Correct 1 ms 364 KB n = 16
36 Correct 1 ms 364 KB n = 15
37 Correct 1 ms 384 KB n = 8
38 Correct 1 ms 364 KB n = 16
39 Correct 1 ms 364 KB n = 16
40 Correct 1 ms 364 KB n = 9
41 Correct 1 ms 364 KB n = 16
42 Correct 1 ms 364 KB n = 16
43 Correct 1 ms 364 KB n = 16
44 Correct 1 ms 364 KB n = 9
45 Correct 1 ms 364 KB n = 15
46 Correct 1 ms 364 KB n = 16
47 Correct 1 ms 364 KB n = 16
48 Correct 1 ms 364 KB n = 16

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 11980 KB n = 199999
2 Correct 174 ms 11980 KB n = 199991
3 Correct 162 ms 11980 KB n = 199993
4 Correct 120 ms 8900 KB n = 152076
5 Correct 72 ms 5920 KB n = 93249
6 Correct 157 ms 10364 KB n = 199910
7 Correct 165 ms 11212 KB n = 199999
8 Correct 173 ms 10444 KB n = 199997
9 Correct 143 ms 10156 KB n = 171294
10 Correct 115 ms 8476 KB n = 140872
11 Correct 161 ms 10400 KB n = 199886
12 Correct 174 ms 12108 KB n = 199996
13 Correct 183 ms 11340 KB n = 200000
14 Correct 191 ms 14540 KB n = 199998
15 Correct 234 ms 14284 KB n = 200000
16 Correct 204 ms 14796 KB n = 199998
17 Correct 166 ms 11980 KB n = 200000
18 Correct 163 ms 11548 KB n = 190000
19 Correct 141 ms 10680 KB n = 177777
20 Correct 90 ms 6108 KB n = 100000
21 Correct 168 ms 11980 KB n = 200000
22 Correct 204 ms 15308 KB n = 200000
23 Correct 209 ms 15332 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB n = 2
2 Correct 1 ms 364 KB n = 2
3 Correct 1 ms 364 KB n = 2
4 Correct 1 ms 364 KB n = 2
5 Correct 1 ms 364 KB n = 2
6 Correct 1 ms 364 KB n = 2
7 Correct 1 ms 364 KB n = 3
8 Correct 1 ms 364 KB n = 3
9 Correct 1 ms 364 KB n = 3
10 Correct 1 ms 364 KB n = 8
11 Correct 1 ms 364 KB n = 8
12 Correct 1 ms 364 KB n = 8
13 Correct 1 ms 364 KB n = 8
14 Correct 1 ms 364 KB n = 8
15 Correct 1 ms 364 KB n = 8
16 Correct 1 ms 364 KB n = 8
17 Correct 1 ms 364 KB n = 8
18 Correct 1 ms 364 KB n = 8
19 Correct 1 ms 364 KB n = 3
20 Correct 1 ms 364 KB n = 7
21 Correct 1 ms 364 KB n = 8
22 Correct 1 ms 364 KB n = 8
23 Correct 1 ms 364 KB n = 8
24 Correct 1 ms 364 KB n = 8
25 Correct 1 ms 364 KB n = 8
26 Correct 1 ms 364 KB n = 8
27 Correct 1 ms 364 KB n = 8
28 Correct 1 ms 364 KB n = 8
29 Correct 1 ms 364 KB n = 16
30 Correct 1 ms 364 KB n = 16
31 Correct 1 ms 364 KB n = 16
32 Correct 1 ms 364 KB n = 16
33 Correct 1 ms 364 KB n = 16
34 Correct 1 ms 364 KB n = 16
35 Correct 1 ms 364 KB n = 16
36 Correct 1 ms 364 KB n = 15
37 Correct 1 ms 384 KB n = 8
38 Correct 1 ms 364 KB n = 16
39 Correct 1 ms 364 KB n = 16
40 Correct 1 ms 364 KB n = 9
41 Correct 1 ms 364 KB n = 16
42 Correct 1 ms 364 KB n = 16
43 Correct 1 ms 364 KB n = 16
44 Correct 1 ms 364 KB n = 9
45 Correct 1 ms 364 KB n = 15
46 Correct 1 ms 364 KB n = 16
47 Correct 1 ms 364 KB n = 16
48 Correct 1 ms 364 KB n = 16
49 Correct 161 ms 11980 KB n = 199999
50 Correct 174 ms 11980 KB n = 199991
51 Correct 162 ms 11980 KB n = 199993
52 Correct 120 ms 8900 KB n = 152076
53 Correct 72 ms 5920 KB n = 93249
54 Correct 157 ms 10364 KB n = 199910
55 Correct 165 ms 11212 KB n = 199999
56 Correct 173 ms 10444 KB n = 199997
57 Correct 143 ms 10156 KB n = 171294
58 Correct 115 ms 8476 KB n = 140872
59 Correct 161 ms 10400 KB n = 199886
60 Correct 174 ms 12108 KB n = 199996
61 Correct 183 ms 11340 KB n = 200000
62 Correct 191 ms 14540 KB n = 199998
63 Correct 234 ms 14284 KB n = 200000
64 Correct 204 ms 14796 KB n = 199998
65 Correct 166 ms 11980 KB n = 200000
66 Correct 163 ms 11548 KB n = 190000
67 Correct 141 ms 10680 KB n = 177777
68 Correct 90 ms 6108 KB n = 100000
69 Correct 168 ms 11980 KB n = 200000
70 Correct 204 ms 15308 KB n = 200000
71 Correct 209 ms 15332 KB n = 200000
72 Correct 165 ms 11980 KB n = 200000
73 Correct 178 ms 11980 KB n = 200000
74 Correct 179 ms 11980 KB n = 200000
75 Correct 156 ms 11980 KB n = 200000
76 Correct 201 ms 11980 KB n = 200000
77 Correct 157 ms 10572 KB n = 200000
78 Correct 189 ms 13644 KB n = 200000
79 Correct 158 ms 10956 KB n = 184307
80 Correct 58 ms 4756 KB n = 76040
81 Correct 160 ms 10484 KB n = 199981
82 Correct 182 ms 12024 KB n = 199994
83 Correct 171 ms 11340 KB n = 199996
84 Correct 190 ms 14412 KB n = 199998
85 Correct 196 ms 14388 KB n = 200000
86 Correct 195 ms 14796 KB n = 199998
87 Correct 157 ms 11980 KB n = 200000
88 Correct 171 ms 12108 KB n = 200000
89 Correct 156 ms 11980 KB n = 200000
90 Correct 197 ms 12108 KB n = 200000
91 Correct 210 ms 15308 KB n = 200000
92 Correct 205 ms 15308 KB n = 200000