oj.uz

Submission #600519

# Submission time Handle Problem Language Result Execution time Memory
600519 2022-07-21T01:48:45 Z cheissmart Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 232 ms 19620 KB 
#include "railroad.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

struct DSU {
    vi p, sz;
    DSU(int n) {
        p = vi(n), sz = vi(n, 1), iota(ALL(p), 0);
    }
    int find(int u) {
        return p[u] == u ? u : p[u] = find(p[u]);
    }
    void unite(int u, int v) {
        u = find(u), v = find(v);
        if(u == v) return;
        if(sz[u] > sz[v]) swap(u, v);
        p[u] = v, sz[v] += sz[u];
    }
};  

ll plan_roller_coaster(vi s, vi t) {
    int n = SZ(s);
    vi compress;
    for(int i:s) compress.PB(i);
    for(int i:t) compress.PB(i);
    compress.PB(1), compress.PB(1e9);
    sort(ALL(compress)), compress.resize(unique(ALL(compress)) - compress.begin());
    int m = SZ(compress);
    vi aux(m);

    DSU dsu(m);
    for(int i = 0; i < n; i++) {
        int l = lower_bound(ALL(compress), s[i]) - compress.begin();
        int r = lower_bound(ALL(compress), t[i]) - compress.begin();
        aux[l]++, aux[r]--;
        dsu.unite(l, r);
    }
    ll ans = 0;
    for(int i = 0; i < m - 1; i++) {
        if(aux[i] > 1) {
            ans += 1LL * (aux[i] - 1) * (compress[i + 1] - compress[i]);
            dsu.unite(i, i + 1);
        } else if(aux[i] < 1) {
            dsu.unite(i, i + 1);
        }
        aux[i + 1] += aux[i];
    }
    V<pair<ll, pi>> es;
    for(int i = 0; i < m - 1; i++)
        es.EB(compress[i + 1] - compress[i], pi(i, i + 1));
    sort(ALL(es));
    for(auto[w, uv]:es) {
        auto [u, v] = uv;
        if(dsu.find(u) != dsu.find(v)) {
            dsu.unite(u, v);
            ans += w;
        }
    }
    return ans;
}

Compilation message

railroad.cpp: In function 'll plan_roller_coaster(vi, vi)':
railroad.cpp:68:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |     for(auto[w, uv]:es) {
      |             ^
railroad.cpp:69:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |         auto [u, v] = uv;
      |              ^

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 17988 KB n = 199999
2 Correct 208 ms 18020 KB n = 199991
3 Correct 232 ms 17972 KB n = 199993
4 Correct 152 ms 15804 KB n = 152076
5 Correct 88 ms 8832 KB n = 93249
6 Correct 178 ms 17084 KB n = 199910
7 Correct 217 ms 17916 KB n = 199999
8 Correct 179 ms 17164 KB n = 199997
9 Correct 179 ms 16700 KB n = 171294
10 Correct 141 ms 15268 KB n = 140872
11 Correct 190 ms 17232 KB n = 199886
12 Correct 212 ms 17976 KB n = 199996
13 Correct 179 ms 17344 KB n = 200000
14 Correct 213 ms 17924 KB n = 199998
15 Correct 205 ms 17856 KB n = 200000
16 Correct 193 ms 18028 KB n = 199998
17 Correct 217 ms 18092 KB n = 200000
18 Correct 192 ms 17596 KB n = 190000
19 Correct 178 ms 16904 KB n = 177777
20 Correct 96 ms 9136 KB n = 100000
21 Correct 203 ms 18032 KB n = 200000
22 Correct 230 ms 18112 KB n = 200000
23 Correct 207 ms 17984 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 2
2 Correct 0 ms 212 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 0 ms 212 KB n = 2
5 Correct 0 ms 212 KB n = 2
6 Correct 0 ms 212 KB n = 2
7 Correct 0 ms 212 KB n = 3
8 Correct 0 ms 212 KB n = 3
9 Correct 0 ms 212 KB n = 3
10 Correct 0 ms 212 KB n = 8
11 Correct 0 ms 212 KB n = 8
12 Correct 0 ms 212 KB n = 8
13 Correct 0 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8
16 Correct 0 ms 212 KB n = 8
17 Correct 1 ms 212 KB n = 8
18 Correct 0 ms 212 KB n = 8
19 Correct 1 ms 212 KB n = 3
20 Correct 1 ms 212 KB n = 7
21 Correct 0 ms 212 KB n = 8
22 Correct 0 ms 212 KB n = 8
23 Correct 0 ms 212 KB n = 8
24 Correct 0 ms 212 KB n = 8
25 Correct 0 ms 212 KB n = 8
26 Correct 0 ms 212 KB n = 8
27 Correct 0 ms 212 KB n = 8
28 Correct 0 ms 212 KB n = 8
29 Correct 0 ms 212 KB n = 16
30 Correct 0 ms 212 KB n = 16
31 Correct 0 ms 212 KB n = 16
32 Correct 1 ms 212 KB n = 16
33 Correct 0 ms 212 KB n = 16
34 Correct 0 ms 212 KB n = 16
35 Correct 0 ms 212 KB n = 16
36 Correct 0 ms 212 KB n = 15
37 Correct 0 ms 212 KB n = 8
38 Correct 0 ms 212 KB n = 16
39 Correct 0 ms 212 KB n = 16
40 Correct 0 ms 212 KB n = 9
41 Correct 0 ms 212 KB n = 16
42 Correct 0 ms 212 KB n = 16
43 Correct 0 ms 212 KB n = 16
44 Correct 0 ms 212 KB n = 9
45 Correct 0 ms 212 KB n = 15
46 Correct 0 ms 212 KB n = 16
47 Correct 0 ms 212 KB n = 16
48 Correct 1 ms 212 KB n = 16
49 Correct 211 ms 17988 KB n = 199999
50 Correct 208 ms 18020 KB n = 199991
51 Correct 232 ms 17972 KB n = 199993
52 Correct 152 ms 15804 KB n = 152076
53 Correct 88 ms 8832 KB n = 93249
54 Correct 178 ms 17084 KB n = 199910
55 Correct 217 ms 17916 KB n = 199999
56 Correct 179 ms 17164 KB n = 199997
57 Correct 179 ms 16700 KB n = 171294
58 Correct 141 ms 15268 KB n = 140872
59 Correct 190 ms 17232 KB n = 199886
60 Correct 212 ms 17976 KB n = 199996
61 Correct 179 ms 17344 KB n = 200000
62 Correct 213 ms 17924 KB n = 199998
63 Correct 205 ms 17856 KB n = 200000
64 Correct 193 ms 18028 KB n = 199998
65 Correct 217 ms 18092 KB n = 200000
66 Correct 192 ms 17596 KB n = 190000
67 Correct 178 ms 16904 KB n = 177777
68 Correct 96 ms 9136 KB n = 100000
69 Correct 203 ms 18032 KB n = 200000
70 Correct 230 ms 18112 KB n = 200000
71 Correct 207 ms 17984 KB n = 200000
72 Correct 215 ms 19428 KB n = 200000
73 Correct 221 ms 19516 KB n = 200000
74 Correct 212 ms 19448 KB n = 200000
75 Correct 196 ms 19424 KB n = 200000
76 Correct 218 ms 19620 KB n = 200000
77 Correct 145 ms 13088 KB n = 200000
78 Correct 168 ms 12988 KB n = 200000
79 Correct 195 ms 18688 KB n = 184307
80 Correct 71 ms 8856 KB n = 76040
81 Correct 191 ms 18608 KB n = 199981
82 Correct 196 ms 19460 KB n = 199994
83 Correct 187 ms 18792 KB n = 199996
84 Correct 190 ms 19420 KB n = 199998
85 Correct 192 ms 19208 KB n = 200000
86 Correct 207 ms 19412 KB n = 199998
87 Correct 203 ms 19440 KB n = 200000
88 Correct 229 ms 19556 KB n = 200000
89 Correct 204 ms 19448 KB n = 200000
90 Correct 203 ms 19452 KB n = 200000
91 Correct 226 ms 19596 KB n = 200000
92 Correct 198 ms 19488 KB n = 200000