oj.uz

Submission #603262

# Submission time Handle Problem Language Result Execution time Memory
603262 2022-07-23T19:47:20 Z georgievskiy Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 188 ms 15732 KB 
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

struct DSU {
    vector<int> p;
    DSU(int n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }
    int get(int x) {
        return p[x] = (x == p[x] ? x : get(p[x]));
    }
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return 0;
        p[x] = y;
        return 1;
    }
    void print() {
        for (int i = 0; i < p.size(); i++) cout << get(i) << " "; cout << "\n";
    }
};

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();
    vector<int> a;
    for (int i = 0; i < n; i++) a.push_back(s[i]), a.push_back(t[i]);
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    for (int i = 0; i < n; i++)
        s[i] = lower_bound(a.begin(), a.end(), s[i]) - a.begin(),
        t[i] = lower_bound(a.begin(), a.end(), t[i]) - a.begin();
    int m = a.size();
    a.push_back(2e9);
    vector<int> cs(m), ct(m);
    DSU dsu(m);
    for (int i = 0; i < n; i++)
        cs[s[i]]++, ct[t[i]]++;
    for (int i = 0; i < n; i++)
        dsu.unite(s[i], t[i]);

    int cur = -1;
    ll ans = 0;
    vector<pii> w;
    for (int i = 0; i < m; i++) {
        cur += cs[i] - ct[i];
        if (cur > 0) {
            ans += 1ll * cur * (a[i + 1] - a[i]);
            //cur = 0;
            dsu.unite(i, i + 1);
        }
        if (i == m - 1) continue;
        if (cur < 0) dsu.unite(i, i + 1);
        if (cur == 0) w.push_back({a[i + 1] - a[i], i});
    }
    //dsu.print();
    sort(w.begin(), w.end());
    for (auto e : w) {
        int u = e.second, v = e.second + 1;
        if (dsu.unite(u, v)) ans += e.first;
    }
    return ans;
}

Compilation message

railroad.cpp: In member function 'void DSU::print()':
railroad.cpp:23:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for (int i = 0; i < p.size(); i++) cout << get(i) << " "; cout << "\n";
      |                         ~~^~~~~~~~~~
railroad.cpp:23:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   23 |         for (int i = 0; i < p.size(); i++) cout << get(i) << " "; cout << "\n";
      |         ^~~
railroad.cpp:23:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   23 |         for (int i = 0; i < p.size(); i++) cout << get(i) << " "; cout << "\n";
      |                                                                   ^~~~

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 1 ms 212 KB n = 2
5 Correct 1 ms 296 KB n = 2
6 Correct 1 ms 212 KB n = 2
7 Correct 1 ms 212 KB n = 3
8 Correct 1 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 1 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 0 ms 212 KB n = 8
16 Correct 0 ms 212 KB n = 8
17 Correct 0 ms 212 KB n = 8
18 Correct 0 ms 212 KB n = 8
19 Correct 0 ms 212 KB n = 3
20 Correct 1 ms 212 KB n = 7
21 Correct 1 ms 296 KB n = 8
22 Correct 1 ms 212 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 1 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 1 ms 212 KB n = 2
5 Correct 1 ms 296 KB n = 2
6 Correct 1 ms 212 KB n = 2
7 Correct 1 ms 212 KB n = 3
8 Correct 1 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 1 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 0 ms 212 KB n = 8
16 Correct 0 ms 212 KB n = 8
17 Correct 0 ms 212 KB n = 8
18 Correct 0 ms 212 KB n = 8
19 Correct 0 ms 212 KB n = 3
20 Correct 1 ms 212 KB n = 7
21 Correct 1 ms 296 KB n = 8
22 Correct 1 ms 212 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 1 ms 212 KB n = 8
25 Correct 0 ms 212 KB n = 8
26 Correct 1 ms 296 KB n = 8
27 Correct 0 ms 212 KB n = 8
28 Correct 1 ms 212 KB n = 8
29 Correct 1 ms 212 KB n = 16
30 Correct 1 ms 212 KB n = 16
31 Correct 1 ms 212 KB n = 16
32 Correct 1 ms 212 KB n = 16
33 Correct 1 ms 212 KB n = 16
34 Correct 1 ms 300 KB n = 16
35 Correct 1 ms 212 KB n = 16
36 Correct 1 ms 212 KB n = 15
37 Correct 1 ms 212 KB n = 8
38 Correct 1 ms 212 KB n = 16
39 Correct 1 ms 212 KB n = 16
40 Correct 1 ms 212 KB n = 9
41 Correct 1 ms 300 KB n = 16
42 Correct 1 ms 212 KB n = 16
43 Correct 1 ms 296 KB n = 16
44 Correct 0 ms 212 KB n = 9
45 Correct 1 ms 300 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 171 ms 13696 KB n = 199999
2 Correct 158 ms 13628 KB n = 199991
3 Correct 157 ms 13692 KB n = 199993
4 Correct 132 ms 10204 KB n = 152076
5 Correct 71 ms 6596 KB n = 93249
6 Correct 131 ms 11688 KB n = 199910
7 Correct 135 ms 12924 KB n = 199999
8 Correct 134 ms 11744 KB n = 199997
9 Correct 131 ms 11592 KB n = 171294
10 Correct 107 ms 9680 KB n = 140872
11 Correct 142 ms 11824 KB n = 199886
12 Correct 141 ms 13336 KB n = 199996
13 Correct 138 ms 12704 KB n = 200000
14 Correct 151 ms 15616 KB n = 199998
15 Correct 160 ms 15500 KB n = 200000
16 Correct 172 ms 15636 KB n = 199998
17 Correct 147 ms 15064 KB n = 200000
18 Correct 138 ms 12352 KB n = 190000
19 Correct 127 ms 13692 KB n = 177777
20 Correct 68 ms 7072 KB n = 100000
21 Correct 154 ms 12684 KB n = 200000
22 Correct 183 ms 15636 KB n = 200000
23 Correct 178 ms 15656 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 1 ms 212 KB n = 2
5 Correct 1 ms 296 KB n = 2
6 Correct 1 ms 212 KB n = 2
7 Correct 1 ms 212 KB n = 3
8 Correct 1 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 1 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 0 ms 212 KB n = 8
16 Correct 0 ms 212 KB n = 8
17 Correct 0 ms 212 KB n = 8
18 Correct 0 ms 212 KB n = 8
19 Correct 0 ms 212 KB n = 3
20 Correct 1 ms 212 KB n = 7
21 Correct 1 ms 296 KB n = 8
22 Correct 1 ms 212 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 1 ms 212 KB n = 8
25 Correct 0 ms 212 KB n = 8
26 Correct 1 ms 296 KB n = 8
27 Correct 0 ms 212 KB n = 8
28 Correct 1 ms 212 KB n = 8
29 Correct 1 ms 212 KB n = 16
30 Correct 1 ms 212 KB n = 16
31 Correct 1 ms 212 KB n = 16
32 Correct 1 ms 212 KB n = 16
33 Correct 1 ms 212 KB n = 16
34 Correct 1 ms 300 KB n = 16
35 Correct 1 ms 212 KB n = 16
36 Correct 1 ms 212 KB n = 15
37 Correct 1 ms 212 KB n = 8
38 Correct 1 ms 212 KB n = 16
39 Correct 1 ms 212 KB n = 16
40 Correct 1 ms 212 KB n = 9
41 Correct 1 ms 300 KB n = 16
42 Correct 1 ms 212 KB n = 16
43 Correct 1 ms 296 KB n = 16
44 Correct 0 ms 212 KB n = 9
45 Correct 1 ms 300 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 171 ms 13696 KB n = 199999
50 Correct 158 ms 13628 KB n = 199991
51 Correct 157 ms 13692 KB n = 199993
52 Correct 132 ms 10204 KB n = 152076
53 Correct 71 ms 6596 KB n = 93249
54 Correct 131 ms 11688 KB n = 199910
55 Correct 135 ms 12924 KB n = 199999
56 Correct 134 ms 11744 KB n = 199997
57 Correct 131 ms 11592 KB n = 171294
58 Correct 107 ms 9680 KB n = 140872
59 Correct 142 ms 11824 KB n = 199886
60 Correct 141 ms 13336 KB n = 199996
61 Correct 138 ms 12704 KB n = 200000
62 Correct 151 ms 15616 KB n = 199998
63 Correct 160 ms 15500 KB n = 200000
64 Correct 172 ms 15636 KB n = 199998
65 Correct 147 ms 15064 KB n = 200000
66 Correct 138 ms 12352 KB n = 190000
67 Correct 127 ms 13692 KB n = 177777
68 Correct 68 ms 7072 KB n = 100000
69 Correct 154 ms 12684 KB n = 200000
70 Correct 183 ms 15636 KB n = 200000
71 Correct 178 ms 15656 KB n = 200000
72 Correct 158 ms 12884 KB n = 200000
73 Correct 182 ms 12684 KB n = 200000
74 Correct 155 ms 12744 KB n = 200000
75 Correct 140 ms 12676 KB n = 200000
76 Correct 149 ms 12696 KB n = 200000
77 Correct 125 ms 10248 KB n = 200000
78 Correct 149 ms 13348 KB n = 200000
79 Correct 156 ms 12024 KB n = 184307
80 Correct 54 ms 5412 KB n = 76040
81 Correct 130 ms 11808 KB n = 199981
82 Correct 148 ms 13320 KB n = 199994
83 Correct 139 ms 12708 KB n = 199996
84 Correct 149 ms 15540 KB n = 199998
85 Correct 153 ms 15504 KB n = 200000
86 Correct 167 ms 15624 KB n = 199998
87 Correct 140 ms 15064 KB n = 200000
88 Correct 141 ms 13244 KB n = 200000
89 Correct 167 ms 15044 KB n = 200000
90 Correct 153 ms 12664 KB n = 200000
91 Correct 177 ms 15664 KB n = 200000
92 Correct 188 ms 15732 KB n = 200000