oj.uz

Submission #66311

# Submission time Handle Problem Language Result Execution time Memory
66311 2018-08-10T08:05:02 Z aquablitz11 Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 302 ms 24732 KB 
#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int N = 400010;
const int INF = 1e9+1;

int c;
vector<int> coord;
inline int pos(int x) { return upper_bound(coord.begin(), coord.end(), x) - coord.begin(); }
inline int &get(int i) { return coord[i-1]; }
int qs[N], par[N];

int root(int u) {
    if (!par[u]) return u;
    return par[u] = root(par[u]);
}

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

long long plan_roller_coaster(vector<int> s, vector<int> t)
{
    // graph construction
    int n = s.size();
    coord.insert(coord.end(), s.begin(), s.end());
    coord.insert(coord.end(), t.begin(), t.end());
    coord.push_back(0);
    coord.push_back(INF);
    sort(coord.begin(), coord.end());
    coord.resize(unique(coord.begin(), coord.end())-coord.begin());
    c = coord.size();
    qs[pos(0)] -= 1;
    qs[pos(INF)] += 1;
    for (int i = 0; i < n; ++i) {
        int a = s[i], b = t[i], v = 1;
        if (a > b) swap(a, b), v = -1;
        a = pos(a), b = pos(b);
        merge(a, b);
        qs[a] += v;
        qs[b] -= v;
    }

    // cost calculation and dsu
    ll cost = 0;
    vector<pii> E;
    for (int i = 1; i <= c-1; ++i) {
        qs[i] += qs[i-1];
        ll dist = get(i+1)-get(i);
        cost += max(qs[i]*dist, 0ll);
        if (qs[i] != 0)
            merge(i, i+1);
        else
            E.push_back(pii(dist, i));
    }
    sort(E.begin(), E.end());
    for (auto e : E) {
        if (merge(e.second, e.second+1))
            cost += e.first;
    }

    return cost;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 8584 KB n = 199999
2 Correct 246 ms 11472 KB n = 199991
3 Correct 232 ms 14224 KB n = 199993
4 Correct 168 ms 14224 KB n = 152076
5 Correct 104 ms 14224 KB n = 93249
6 Correct 197 ms 17944 KB n = 199910
7 Correct 216 ms 19612 KB n = 199999
8 Correct 196 ms 19612 KB n = 199997
9 Correct 198 ms 19612 KB n = 171294
10 Correct 158 ms 19612 KB n = 140872
11 Correct 204 ms 19612 KB n = 199886
12 Correct 209 ms 20720 KB n = 199996
13 Correct 199 ms 20720 KB n = 200000
14 Correct 214 ms 24568 KB n = 199998
15 Correct 302 ms 24568 KB n = 200000
16 Correct 218 ms 24568 KB n = 199998
17 Correct 207 ms 24568 KB n = 200000
18 Correct 193 ms 24568 KB n = 190000
19 Correct 217 ms 24568 KB n = 177777
20 Correct 98 ms 24568 KB n = 100000
21 Correct 210 ms 24568 KB n = 200000
22 Correct 246 ms 24568 KB n = 200000
23 Correct 267 ms 24568 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB n = 2
2 Correct 3 ms 484 KB n = 2
3 Correct 3 ms 484 KB n = 2
4 Correct 2 ms 484 KB n = 2
5 Correct 3 ms 484 KB n = 2
6 Correct 3 ms 512 KB n = 2
7 Correct 2 ms 544 KB n = 3
8 Correct 2 ms 544 KB n = 3
9 Correct 2 ms 544 KB n = 3
10 Correct 2 ms 620 KB n = 8
11 Correct 3 ms 620 KB n = 8
12 Correct 2 ms 620 KB n = 8
13 Correct 3 ms 620 KB n = 8
14 Correct 2 ms 744 KB n = 8
15 Correct 2 ms 744 KB n = 8
16 Correct 3 ms 744 KB n = 8
17 Correct 2 ms 744 KB n = 8
18 Correct 3 ms 744 KB n = 8
19 Correct 2 ms 744 KB n = 3
20 Correct 2 ms 744 KB n = 7
21 Correct 2 ms 744 KB n = 8
22 Correct 2 ms 744 KB n = 8
23 Correct 2 ms 744 KB n = 8
24 Correct 2 ms 744 KB n = 8
25 Correct 2 ms 744 KB n = 8
26 Correct 2 ms 744 KB n = 8
27 Correct 2 ms 744 KB n = 8
28 Correct 3 ms 744 KB n = 8
29 Correct 2 ms 748 KB n = 16
30 Correct 3 ms 748 KB n = 16
31 Correct 2 ms 748 KB n = 16
32 Correct 2 ms 748 KB n = 16
33 Correct 2 ms 748 KB n = 16
34 Correct 3 ms 748 KB n = 16
35 Correct 2 ms 748 KB n = 16
36 Correct 3 ms 748 KB n = 15
37 Correct 3 ms 748 KB n = 8
38 Correct 3 ms 748 KB n = 16
39 Correct 3 ms 748 KB n = 16
40 Correct 2 ms 748 KB n = 9
41 Correct 3 ms 748 KB n = 16
42 Correct 2 ms 748 KB n = 16
43 Correct 2 ms 748 KB n = 16
44 Correct 3 ms 748 KB n = 9
45 Correct 2 ms 748 KB n = 15
46 Correct 2 ms 748 KB n = 16
47 Correct 3 ms 748 KB n = 16
48 Correct 2 ms 748 KB n = 16
49 Correct 226 ms 8584 KB n = 199999
50 Correct 246 ms 11472 KB n = 199991
51 Correct 232 ms 14224 KB n = 199993
52 Correct 168 ms 14224 KB n = 152076
53 Correct 104 ms 14224 KB n = 93249
54 Correct 197 ms 17944 KB n = 199910
55 Correct 216 ms 19612 KB n = 199999
56 Correct 196 ms 19612 KB n = 199997
57 Correct 198 ms 19612 KB n = 171294
58 Correct 158 ms 19612 KB n = 140872
59 Correct 204 ms 19612 KB n = 199886
60 Correct 209 ms 20720 KB n = 199996
61 Correct 199 ms 20720 KB n = 200000
62 Correct 214 ms 24568 KB n = 199998
63 Correct 302 ms 24568 KB n = 200000
64 Correct 218 ms 24568 KB n = 199998
65 Correct 207 ms 24568 KB n = 200000
66 Correct 193 ms 24568 KB n = 190000
67 Correct 217 ms 24568 KB n = 177777
68 Correct 98 ms 24568 KB n = 100000
69 Correct 210 ms 24568 KB n = 200000
70 Correct 246 ms 24568 KB n = 200000
71 Correct 267 ms 24568 KB n = 200000
72 Correct 254 ms 24568 KB n = 200000
73 Correct 219 ms 24568 KB n = 200000
74 Correct 216 ms 24568 KB n = 200000
75 Correct 203 ms 24568 KB n = 200000
76 Correct 214 ms 24568 KB n = 200000
77 Correct 195 ms 24568 KB n = 200000
78 Correct 223 ms 24568 KB n = 200000
79 Correct 195 ms 24568 KB n = 184307
80 Correct 77 ms 24568 KB n = 76040
81 Correct 201 ms 24568 KB n = 199981
82 Correct 217 ms 24568 KB n = 199994
83 Correct 208 ms 24568 KB n = 199996
84 Correct 220 ms 24732 KB n = 199998
85 Correct 206 ms 24732 KB n = 200000
86 Correct 226 ms 24732 KB n = 199998
87 Correct 248 ms 24732 KB n = 200000
88 Correct 218 ms 24732 KB n = 200000
89 Correct 206 ms 24732 KB n = 200000
90 Correct 202 ms 24732 KB n = 200000
91 Correct 253 ms 24732 KB n = 200000
92 Correct 285 ms 24732 KB n = 200000