oj.uz

Submission #163322

# Submission time Handle Problem Language Result Execution time Memory
163322 2019-11-12T15:17:47 Z dolphingarlic Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 309 ms 19948 KB 
#include "railroad.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;
typedef long long ll;

int balance[404040], din[404040], dout[404040];
vector<pair<int, pair<int, int>>> edges;

int cmp[404040];
int find(int a) {
    while (cmp[a] != a) cmp[a] = cmp[cmp[a]], a = cmp[a];
    return a;
}
void onion(int a, int b) { cmp[find(a)] = cmp[find(b)]; }

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = s.size();

    FOR(i, 0, n) {
        balance[i * 2] = s[i];
        balance[i * 2 + 1] = t[i];
    }
    balance[2 * n] = 1;
    balance[2 * n + 1] = 2e9;

    sort(balance, balance + 2 * n + 2);
    FOR(i, 0, 2 * n + 2) cmp[i] = i;

    FOR(i, 0, n) {
        s[i] = lower_bound(balance, balance + 2 * n + 2, s[i]) - balance;
        t[i] = lower_bound(balance, balance + 2 * n + 2, t[i]) - balance;

        din[t[i]]++;
        dout[s[i]]++;
        onion(t[i], s[i]);
    }
    din[0]++;
    dout[2 * n + 1]++;
    onion(0, 2 * n + 1);

    ll ans = 0, sm = 0;
    FOR(i, 0, 2 * n + 1) {
        sm += dout[i] - din[i];
        if (sm < 0)
            onion(i, i + 1);
        else if (sm == 0)
            edges.push_back({balance[i + 1] - balance[i], {i, i + 1}});
        else {
            ans += sm * (balance[i + 1] - balance[i]);
            onion(i, i + 1);
        }
    }

    sort(edges.begin(), edges.end());
    for (auto& i : edges) {
        if (find(i.second.first) != find(i.second.second)) {
            onion(i.second.first, i.second.second);
            ans += i.first;
        }
    }

    return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 9860 KB n = 199999
2 Correct 243 ms 9692 KB n = 199991
3 Correct 233 ms 9848 KB n = 199993
4 Correct 170 ms 7544 KB n = 152076
5 Correct 103 ms 4728 KB n = 93249
6 Correct 195 ms 9720 KB n = 199910
7 Correct 198 ms 9720 KB n = 199999
8 Correct 194 ms 9900 KB n = 199997
9 Correct 216 ms 8440 KB n = 171294
10 Correct 162 ms 6876 KB n = 140872
11 Correct 202 ms 9884 KB n = 199886
12 Correct 208 ms 10272 KB n = 199996
13 Correct 196 ms 10268 KB n = 200000
14 Correct 222 ms 12908 KB n = 199998
15 Correct 216 ms 13036 KB n = 200000
16 Correct 229 ms 13040 KB n = 199998
17 Correct 204 ms 8184 KB n = 200000
18 Correct 206 ms 9372 KB n = 190000
19 Correct 181 ms 7292 KB n = 177777
20 Correct 100 ms 5040 KB n = 100000
21 Correct 223 ms 9692 KB n = 200000
22 Correct 267 ms 13036 KB n = 200000
23 Correct 260 ms 12996 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 2
2 Correct 2 ms 376 KB n = 2
3 Correct 2 ms 376 KB n = 2
4 Correct 2 ms 376 KB n = 2
5 Correct 2 ms 376 KB n = 2
6 Correct 2 ms 376 KB n = 2
7 Correct 2 ms 376 KB n = 3
8 Correct 2 ms 376 KB n = 3
9 Correct 2 ms 376 KB n = 3
10 Correct 2 ms 376 KB n = 8
11 Correct 2 ms 376 KB n = 8
12 Correct 2 ms 376 KB n = 8
13 Correct 2 ms 376 KB n = 8
14 Correct 2 ms 380 KB n = 8
15 Correct 2 ms 376 KB n = 8
16 Correct 2 ms 376 KB n = 8
17 Correct 2 ms 376 KB n = 8
18 Correct 2 ms 376 KB n = 8
19 Correct 2 ms 376 KB n = 3
20 Correct 2 ms 376 KB n = 7
21 Correct 2 ms 376 KB n = 8
22 Correct 2 ms 376 KB n = 8
23 Correct 2 ms 376 KB n = 8
24 Correct 2 ms 376 KB n = 8
25 Correct 2 ms 376 KB n = 8
26 Correct 2 ms 376 KB n = 8
27 Correct 2 ms 376 KB n = 8
28 Correct 2 ms 376 KB n = 8
29 Correct 2 ms 376 KB n = 16
30 Correct 2 ms 376 KB n = 16
31 Correct 2 ms 376 KB n = 16
32 Correct 2 ms 376 KB n = 16
33 Correct 2 ms 376 KB n = 16
34 Correct 2 ms 376 KB n = 16
35 Correct 2 ms 376 KB n = 16
36 Correct 2 ms 376 KB n = 15
37 Correct 2 ms 380 KB n = 8
38 Correct 2 ms 376 KB n = 16
39 Correct 2 ms 376 KB n = 16
40 Correct 2 ms 376 KB n = 9
41 Correct 2 ms 376 KB n = 16
42 Correct 2 ms 376 KB n = 16
43 Correct 2 ms 380 KB n = 16
44 Correct 2 ms 376 KB n = 9
45 Correct 2 ms 376 KB n = 15
46 Correct 2 ms 376 KB n = 16
47 Correct 2 ms 380 KB n = 16
48 Correct 2 ms 376 KB n = 16
49 Correct 231 ms 9860 KB n = 199999
50 Correct 243 ms 9692 KB n = 199991
51 Correct 233 ms 9848 KB n = 199993
52 Correct 170 ms 7544 KB n = 152076
53 Correct 103 ms 4728 KB n = 93249
54 Correct 195 ms 9720 KB n = 199910
55 Correct 198 ms 9720 KB n = 199999
56 Correct 194 ms 9900 KB n = 199997
57 Correct 216 ms 8440 KB n = 171294
58 Correct 162 ms 6876 KB n = 140872
59 Correct 202 ms 9884 KB n = 199886
60 Correct 208 ms 10272 KB n = 199996
61 Correct 196 ms 10268 KB n = 200000
62 Correct 222 ms 12908 KB n = 199998
63 Correct 216 ms 13036 KB n = 200000
64 Correct 229 ms 13040 KB n = 199998
65 Correct 204 ms 8184 KB n = 200000
66 Correct 206 ms 9372 KB n = 190000
67 Correct 181 ms 7292 KB n = 177777
68 Correct 100 ms 5040 KB n = 100000
69 Correct 223 ms 9692 KB n = 200000
70 Correct 267 ms 13036 KB n = 200000
71 Correct 260 ms 12996 KB n = 200000
72 Correct 231 ms 13584 KB n = 200000
73 Correct 242 ms 13688 KB n = 200000
74 Correct 309 ms 13708 KB n = 200000
75 Correct 221 ms 12072 KB n = 200000
76 Correct 219 ms 12024 KB n = 200000
77 Correct 206 ms 13560 KB n = 200000
78 Correct 255 ms 19948 KB n = 200000
79 Correct 211 ms 12408 KB n = 184307
80 Correct 83 ms 5372 KB n = 76040
81 Correct 194 ms 12508 KB n = 199981
82 Correct 203 ms 13496 KB n = 199994
83 Correct 190 ms 13212 KB n = 199996
84 Correct 225 ms 16092 KB n = 199998
85 Correct 218 ms 16108 KB n = 200000
86 Correct 236 ms 16364 KB n = 199998
87 Correct 213 ms 12024 KB n = 200000
88 Correct 224 ms 13576 KB n = 200000
89 Correct 214 ms 12028 KB n = 200000
90 Correct 218 ms 13560 KB n = 200000
91 Correct 268 ms 16776 KB n = 200000
92 Correct 259 ms 16876 KB n = 200000