oj.uz

답안 #388614

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
388614 2021-04-12T09:13:26 Z ParsaAlizadeh Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 258 ms 17224 KB 
#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;

typedef long long ll;

struct DSU {
    int n;
    vector<int> par;

    DSU(int n) : n(n), par(n, -1) {}

    int find(int u) {
        return par[u] == -1 ? u : par[u] = find(par[u]);
    }

    bool merge(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v)
            return false;
        par[v] = u;
        return true;
    }
};

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    int const n = (int) s.size();
    vector<int> comp(begin(s), end(s));
    comp.insert(end(comp), begin(t), end(t));
    sort(begin(comp), end(comp));
    comp.erase(unique(begin(comp), end(comp)), end(comp));
    
    int const m = (int) comp.size();
    vector<int> ps(m);
    DSU dsu(m);
    ll ans = 0;

    for (int i = 0; i < n; i++) {
        int l = lower_bound(begin(comp), end(comp), s[i]) - begin(comp);
        int r = lower_bound(begin(comp), end(comp), t[i]) - begin(comp);
        ps[l]++; ps[r]--;
        dsu.merge(l, r);
    }
    ps[m - 1]++; ps[0]--;
    partial_sum(begin(ps), end(ps), begin(ps));
    
    vector<pair<int, int>> edges;
    for (int i = 0; i + 1 < m; i++) {
        if (ps[i] > 0)
            ans += (ll) ps[i] * (comp[i + 1] - comp[i]);
        if (ps[i] != 0)
            dsu.merge(i, i + 1);
        edges.emplace_back(comp[i + 1] - comp[i], i);
    }
    sort(begin(edges), end(edges));
    for (auto & e : edges) {
        if (dsu.merge(e.second, e.second + 1))
            ans += e.first;
    }
    return ans;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB n = 2
2 Correct 1 ms 204 KB n = 2
3 Correct 0 ms 204 KB n = 2
4 Correct 1 ms 292 KB n = 2
5 Correct 1 ms 204 KB n = 2
6 Correct 1 ms 204 KB n = 2
7 Correct 1 ms 204 KB n = 3
8 Correct 1 ms 292 KB n = 3
9 Correct 1 ms 204 KB n = 3
10 Correct 1 ms 204 KB n = 8
11 Correct 1 ms 204 KB n = 8
12 Correct 1 ms 204 KB n = 8
13 Correct 1 ms 204 KB n = 8
14 Correct 1 ms 204 KB n = 8
15 Correct 1 ms 204 KB n = 8
16 Correct 1 ms 204 KB n = 8
17 Correct 1 ms 204 KB n = 8
18 Correct 0 ms 204 KB n = 8
19 Correct 1 ms 204 KB n = 3
20 Correct 1 ms 204 KB n = 7
21 Correct 1 ms 204 KB n = 8
22 Correct 1 ms 204 KB n = 8
23 Correct 1 ms 204 KB n = 8
24 Correct 1 ms 300 KB n = 8
25 Correct 1 ms 204 KB n = 8

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB n = 2
2 Correct 1 ms 204 KB n = 2
3 Correct 0 ms 204 KB n = 2
4 Correct 1 ms 292 KB n = 2
5 Correct 1 ms 204 KB n = 2
6 Correct 1 ms 204 KB n = 2
7 Correct 1 ms 204 KB n = 3
8 Correct 1 ms 292 KB n = 3
9 Correct 1 ms 204 KB n = 3
10 Correct 1 ms 204 KB n = 8
11 Correct 1 ms 204 KB n = 8
12 Correct 1 ms 204 KB n = 8
13 Correct 1 ms 204 KB n = 8
14 Correct 1 ms 204 KB n = 8
15 Correct 1 ms 204 KB n = 8
16 Correct 1 ms 204 KB n = 8
17 Correct 1 ms 204 KB n = 8
18 Correct 0 ms 204 KB n = 8
19 Correct 1 ms 204 KB n = 3
20 Correct 1 ms 204 KB n = 7
21 Correct 1 ms 204 KB n = 8
22 Correct 1 ms 204 KB n = 8
23 Correct 1 ms 204 KB n = 8
24 Correct 1 ms 300 KB n = 8
25 Correct 1 ms 204 KB n = 8
26 Correct 1 ms 292 KB n = 8
27 Correct 1 ms 204 KB n = 8
28 Correct 1 ms 304 KB n = 8
29 Correct 1 ms 204 KB n = 16
30 Correct 1 ms 204 KB n = 16
31 Correct 1 ms 204 KB n = 16
32 Correct 1 ms 204 KB n = 16
33 Correct 1 ms 296 KB n = 16
34 Correct 0 ms 204 KB n = 16
35 Correct 1 ms 204 KB n = 16
36 Correct 1 ms 256 KB n = 15
37 Correct 1 ms 208 KB n = 8
38 Correct 1 ms 296 KB n = 16
39 Correct 1 ms 204 KB n = 16
40 Correct 1 ms 204 KB n = 9
41 Correct 1 ms 204 KB n = 16
42 Correct 1 ms 204 KB n = 16
43 Correct 1 ms 204 KB n = 16
44 Correct 1 ms 204 KB n = 9
45 Correct 1 ms 204 KB n = 15
46 Correct 1 ms 204 KB n = 16
47 Correct 1 ms 204 KB n = 16
48 Correct 1 ms 204 KB n = 16

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 217 ms 13256 KB n = 199999
2 Correct 242 ms 13488 KB n = 199991
3 Correct 258 ms 17052 KB n = 199993
4 Correct 167 ms 13988 KB n = 152076
5 Correct 100 ms 8272 KB n = 93249
6 Correct 203 ms 15536 KB n = 199910
7 Correct 216 ms 16292 KB n = 199999
8 Correct 197 ms 15464 KB n = 199997
9 Correct 193 ms 15392 KB n = 171294
10 Correct 153 ms 12736 KB n = 140872
11 Correct 204 ms 15424 KB n = 199886
12 Correct 229 ms 16436 KB n = 199996
13 Correct 206 ms 15664 KB n = 200000
14 Correct 238 ms 16164 KB n = 199998
15 Correct 216 ms 16176 KB n = 200000
16 Correct 237 ms 16620 KB n = 199998
17 Correct 221 ms 17060 KB n = 200000
18 Correct 240 ms 16472 KB n = 190000
19 Correct 196 ms 15752 KB n = 177777
20 Correct 112 ms 8724 KB n = 100000
21 Correct 237 ms 17072 KB n = 200000
22 Correct 221 ms 17128 KB n = 200000
23 Correct 222 ms 17084 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB n = 2
2 Correct 1 ms 204 KB n = 2
3 Correct 0 ms 204 KB n = 2
4 Correct 1 ms 292 KB n = 2
5 Correct 1 ms 204 KB n = 2
6 Correct 1 ms 204 KB n = 2
7 Correct 1 ms 204 KB n = 3
8 Correct 1 ms 292 KB n = 3
9 Correct 1 ms 204 KB n = 3
10 Correct 1 ms 204 KB n = 8
11 Correct 1 ms 204 KB n = 8
12 Correct 1 ms 204 KB n = 8
13 Correct 1 ms 204 KB n = 8
14 Correct 1 ms 204 KB n = 8
15 Correct 1 ms 204 KB n = 8
16 Correct 1 ms 204 KB n = 8
17 Correct 1 ms 204 KB n = 8
18 Correct 0 ms 204 KB n = 8
19 Correct 1 ms 204 KB n = 3
20 Correct 1 ms 204 KB n = 7
21 Correct 1 ms 204 KB n = 8
22 Correct 1 ms 204 KB n = 8
23 Correct 1 ms 204 KB n = 8
24 Correct 1 ms 300 KB n = 8
25 Correct 1 ms 204 KB n = 8
26 Correct 1 ms 292 KB n = 8
27 Correct 1 ms 204 KB n = 8
28 Correct 1 ms 304 KB n = 8
29 Correct 1 ms 204 KB n = 16
30 Correct 1 ms 204 KB n = 16
31 Correct 1 ms 204 KB n = 16
32 Correct 1 ms 204 KB n = 16
33 Correct 1 ms 296 KB n = 16
34 Correct 0 ms 204 KB n = 16
35 Correct 1 ms 204 KB n = 16
36 Correct 1 ms 256 KB n = 15
37 Correct 1 ms 208 KB n = 8
38 Correct 1 ms 296 KB n = 16
39 Correct 1 ms 204 KB n = 16
40 Correct 1 ms 204 KB n = 9
41 Correct 1 ms 204 KB n = 16
42 Correct 1 ms 204 KB n = 16
43 Correct 1 ms 204 KB n = 16
44 Correct 1 ms 204 KB n = 9
45 Correct 1 ms 204 KB n = 15
46 Correct 1 ms 204 KB n = 16
47 Correct 1 ms 204 KB n = 16
48 Correct 1 ms 204 KB n = 16
49 Correct 217 ms 13256 KB n = 199999
50 Correct 242 ms 13488 KB n = 199991
51 Correct 258 ms 17052 KB n = 199993
52 Correct 167 ms 13988 KB n = 152076
53 Correct 100 ms 8272 KB n = 93249
54 Correct 203 ms 15536 KB n = 199910
55 Correct 216 ms 16292 KB n = 199999
56 Correct 197 ms 15464 KB n = 199997
57 Correct 193 ms 15392 KB n = 171294
58 Correct 153 ms 12736 KB n = 140872
59 Correct 204 ms 15424 KB n = 199886
60 Correct 229 ms 16436 KB n = 199996
61 Correct 206 ms 15664 KB n = 200000
62 Correct 238 ms 16164 KB n = 199998
63 Correct 216 ms 16176 KB n = 200000
64 Correct 237 ms 16620 KB n = 199998
65 Correct 221 ms 17060 KB n = 200000
66 Correct 240 ms 16472 KB n = 190000
67 Correct 196 ms 15752 KB n = 177777
68 Correct 112 ms 8724 KB n = 100000
69 Correct 237 ms 17072 KB n = 200000
70 Correct 221 ms 17128 KB n = 200000
71 Correct 222 ms 17084 KB n = 200000
72 Correct 220 ms 17068 KB n = 200000
73 Correct 239 ms 17224 KB n = 200000
74 Correct 223 ms 17072 KB n = 200000
75 Correct 223 ms 17072 KB n = 200000
76 Correct 227 ms 17056 KB n = 200000
77 Correct 193 ms 13476 KB n = 200000
78 Correct 177 ms 13492 KB n = 200000
79 Correct 210 ms 15972 KB n = 184307
80 Correct 79 ms 6808 KB n = 76040
81 Correct 214 ms 15404 KB n = 199981
82 Correct 221 ms 16428 KB n = 199994
83 Correct 206 ms 15812 KB n = 199996
84 Correct 251 ms 16176 KB n = 199998
85 Correct 227 ms 16224 KB n = 200000
86 Correct 232 ms 16560 KB n = 199998
87 Correct 217 ms 17064 KB n = 200000
88 Correct 227 ms 17068 KB n = 200000
89 Correct 217 ms 17048 KB n = 200000
90 Correct 229 ms 17060 KB n = 200000
91 Correct 228 ms 17124 KB n = 200000
92 Correct 215 ms 17056 KB n = 200000