oj.uz

답안 #163323

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
163323 2019-11-12T15:20:47 Z dolphingarlic Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 444 ms 16164 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 trav[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) {
        trav[i * 2] = s[i];
        trav[i * 2 + 1] = t[i];
    }
    trav[2 * n] = 1;
    trav[2 * n + 1] = 2e9;

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

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

        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({trav[i + 1] - trav[i], {i, i + 1}});
        else {
            ans += sm * (trav[i + 1] - trav[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

# 결과 실행 시간 메모리 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 7 ms 376 KB n = 8
12 Correct 2 ms 348 KB n = 8
13 Correct 3 ms 376 KB n = 8
14 Correct 2 ms 376 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 380 KB n = 7
21 Correct 2 ms 376 KB n = 8
22 Correct 2 ms 380 KB n = 8
23 Correct 4 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

# 결과 실행 시간 메모리 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 7 ms 376 KB n = 8
12 Correct 2 ms 348 KB n = 8
13 Correct 3 ms 376 KB n = 8
14 Correct 2 ms 376 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 380 KB n = 7
21 Correct 2 ms 376 KB n = 8
22 Correct 2 ms 380 KB n = 8
23 Correct 4 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 6 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 376 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 376 KB n = 16
44 Correct 2 ms 376 KB n = 9
45 Correct 2 ms 376 KB n = 15
46 Correct 3 ms 376 KB n = 16
47 Correct 2 ms 376 KB n = 16
48 Correct 2 ms 376 KB n = 16

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 233 ms 9836 KB n = 199999
2 Correct 285 ms 9828 KB n = 199991
3 Correct 229 ms 9848 KB n = 199993
4 Correct 170 ms 7500 KB n = 152076
5 Correct 103 ms 4728 KB n = 93249
6 Correct 195 ms 9720 KB n = 199910
7 Correct 193 ms 9724 KB n = 199999
8 Correct 188 ms 9696 KB n = 199997
9 Correct 189 ms 8312 KB n = 171294
10 Correct 156 ms 6900 KB n = 140872
11 Correct 198 ms 9692 KB n = 199886
12 Correct 207 ms 10296 KB n = 199996
13 Correct 194 ms 10296 KB n = 200000
14 Correct 224 ms 13036 KB n = 199998
15 Correct 216 ms 12980 KB n = 200000
16 Correct 229 ms 12908 KB n = 199998
17 Correct 206 ms 8184 KB n = 200000
18 Correct 206 ms 9456 KB n = 190000
19 Correct 186 ms 7404 KB n = 177777
20 Correct 100 ms 4988 KB n = 100000
21 Correct 224 ms 9828 KB n = 200000
22 Correct 291 ms 13164 KB n = 200000
23 Correct 256 ms 12904 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 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 7 ms 376 KB n = 8
12 Correct 2 ms 348 KB n = 8
13 Correct 3 ms 376 KB n = 8
14 Correct 2 ms 376 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 380 KB n = 7
21 Correct 2 ms 376 KB n = 8
22 Correct 2 ms 380 KB n = 8
23 Correct 4 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 6 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 376 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 376 KB n = 16
44 Correct 2 ms 376 KB n = 9
45 Correct 2 ms 376 KB n = 15
46 Correct 3 ms 376 KB n = 16
47 Correct 2 ms 376 KB n = 16
48 Correct 2 ms 376 KB n = 16
49 Correct 233 ms 9836 KB n = 199999
50 Correct 285 ms 9828 KB n = 199991
51 Correct 229 ms 9848 KB n = 199993
52 Correct 170 ms 7500 KB n = 152076
53 Correct 103 ms 4728 KB n = 93249
54 Correct 195 ms 9720 KB n = 199910
55 Correct 193 ms 9724 KB n = 199999
56 Correct 188 ms 9696 KB n = 199997
57 Correct 189 ms 8312 KB n = 171294
58 Correct 156 ms 6900 KB n = 140872
59 Correct 198 ms 9692 KB n = 199886
60 Correct 207 ms 10296 KB n = 199996
61 Correct 194 ms 10296 KB n = 200000
62 Correct 224 ms 13036 KB n = 199998
63 Correct 216 ms 12980 KB n = 200000
64 Correct 229 ms 12908 KB n = 199998
65 Correct 206 ms 8184 KB n = 200000
66 Correct 206 ms 9456 KB n = 190000
67 Correct 186 ms 7404 KB n = 177777
68 Correct 100 ms 4988 KB n = 100000
69 Correct 224 ms 9828 KB n = 200000
70 Correct 291 ms 13164 KB n = 200000
71 Correct 256 ms 12904 KB n = 200000
72 Correct 243 ms 9788 KB n = 200000
73 Correct 239 ms 9916 KB n = 200000
74 Correct 264 ms 9876 KB n = 200000
75 Correct 224 ms 8224 KB n = 200000
76 Correct 207 ms 8256 KB n = 200000
77 Correct 201 ms 9820 KB n = 200000
78 Correct 444 ms 16164 KB n = 200000
79 Correct 208 ms 9024 KB n = 184307
80 Correct 81 ms 3960 KB n = 76040
81 Correct 195 ms 9720 KB n = 199981
82 Correct 201 ms 10296 KB n = 199994
83 Correct 197 ms 10368 KB n = 199996
84 Correct 218 ms 13036 KB n = 199998
85 Correct 236 ms 12972 KB n = 200000
86 Correct 233 ms 13036 KB n = 199998
87 Correct 214 ms 8264 KB n = 200000
88 Correct 227 ms 9820 KB n = 200000
89 Correct 218 ms 8348 KB n = 200000
90 Correct 225 ms 9720 KB n = 200000
91 Correct 261 ms 13036 KB n = 200000
92 Correct 259 ms 12908 KB n = 200000