oj.uz

Submission #515132

# Submission time Handle Problem Language Result Execution time Memory
515132 2022-01-19T03:45:49 Z SHZhang Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 150 ms 17432 KB 
#include "railroad.h"
#include <algorithm>
#include <utility>

using namespace std;

vector<pair<int, int> > locs;

int uf[400005];
int pre[400005];

int fin(int x)
{
    if (uf[x] == x) return x;
    return uf[x] = fin(uf[x]);
}

void un(int x, int y)
{
    x = fin(x); y = fin(y);
    if (x != y) uf[x] = y;
}

long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = (int)s.size();
    for (int i = 0; i < 2 * n; i++) {
        uf[i] = i; pre[i] = -1;
    }
    for (int i = 0; i < n; i++) locs.push_back(make_pair(s[i], i + 1));
    for (int i = 0; i < n; i++) locs.push_back(make_pair(t[i], -i - 1));
    sort(locs.begin(), locs.end());
    for (int i = 0; i < 2 * n; i++) {
        int idx;
        if (locs[i].second < 0) {
            idx = -locs[i].second - 1;
        } else {
            idx = locs[i].second - 1;
        }
        //printf("! %d %d\n", locs[i].first, idx);
        if (pre[idx] != -1) {
            un(i, pre[idx]);
            //printf("! %d %d\n", i, pre[idx]);
        } else {
            pre[idx] = i;
        }
    }
    int rightcnt = 1;
    vector<pair<int, int> > edges;
    long long ans = 0;
    for (int i = 0; i < 2 * n; i++) {
        if (locs[i].second < 0) {
            rightcnt++;
        } else {
            rightcnt--;
        }
        if (!rightcnt) {
            edges.push_back(
                make_pair(locs[i+1].first - locs[i].first, i));
        } else if (i != 2 * n - 1) {
            un(i, i+1);
            //printf("add %d %d\n", i, rightcnt);
            if (rightcnt < 0) ans += (long long)(-rightcnt) *
                (long long)(locs[i+1].first - locs[i].first);
        }
    }
    sort(edges.begin(), edges.end());
    for (int i = 0; i < edges.size(); i++) {
        if (fin(edges[i].second) != fin(edges[i].second + 1)) {
            ans += (long long)edges[i].first;
            un(edges[i].second, edges[i].second + 1);
        }
    }
    return ans;
}

Compilation message

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < edges.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB n = 2
2 Correct 0 ms 272 KB n = 2
3 Correct 0 ms 280 KB n = 2
4 Correct 1 ms 208 KB n = 2
5 Correct 0 ms 288 KB n = 2
6 Correct 1 ms 208 KB n = 2
7 Correct 1 ms 208 KB n = 3
8 Correct 0 ms 208 KB n = 3
9 Correct 0 ms 208 KB n = 3
10 Correct 0 ms 268 KB n = 8
11 Correct 0 ms 208 KB n = 8
12 Correct 0 ms 292 KB n = 8
13 Correct 0 ms 288 KB n = 8
14 Correct 0 ms 208 KB n = 8
15 Correct 0 ms 208 KB n = 8
16 Correct 0 ms 208 KB n = 8
17 Correct 0 ms 296 KB n = 8
18 Correct 0 ms 208 KB n = 8
19 Correct 1 ms 288 KB n = 3
20 Correct 0 ms 208 KB n = 7
21 Correct 1 ms 288 KB n = 8
22 Correct 0 ms 208 KB n = 8
23 Correct 0 ms 208 KB n = 8
24 Correct 0 ms 208 KB n = 8
25 Correct 0 ms 208 KB n = 8

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 14604 KB n = 199999
2 Correct 104 ms 14616 KB n = 199991
3 Correct 100 ms 14628 KB n = 199993
4 Correct 73 ms 11812 KB n = 152076
5 Correct 49 ms 7132 KB n = 93249
6 Correct 92 ms 13464 KB n = 199910
7 Correct 99 ms 13852 KB n = 199999
8 Correct 94 ms 13464 KB n = 199997
9 Correct 93 ms 12948 KB n = 171294
10 Correct 70 ms 11596 KB n = 140872
11 Correct 99 ms 13464 KB n = 199886
12 Correct 100 ms 13984 KB n = 199996
13 Correct 98 ms 13608 KB n = 200000
14 Correct 110 ms 17364 KB n = 199998
15 Correct 117 ms 16932 KB n = 200000
16 Correct 117 ms 17164 KB n = 199998
17 Correct 87 ms 16304 KB n = 200000
18 Correct 89 ms 14140 KB n = 190000
19 Correct 81 ms 14440 KB n = 177777
20 Correct 51 ms 7436 KB n = 100000
21 Correct 95 ms 14628 KB n = 200000
22 Correct 129 ms 17104 KB n = 200000
23 Correct 123 ms 17156 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB n = 2
2 Correct 0 ms 272 KB n = 2
3 Correct 0 ms 280 KB n = 2
4 Correct 1 ms 208 KB n = 2
5 Correct 0 ms 288 KB n = 2
6 Correct 1 ms 208 KB n = 2
7 Correct 1 ms 208 KB n = 3
8 Correct 0 ms 208 KB n = 3
9 Correct 0 ms 208 KB n = 3
10 Correct 0 ms 268 KB n = 8
11 Correct 0 ms 208 KB n = 8
12 Correct 0 ms 292 KB n = 8
13 Correct 0 ms 288 KB n = 8
14 Correct 0 ms 208 KB n = 8
15 Correct 0 ms 208 KB n = 8
16 Correct 0 ms 208 KB n = 8
17 Correct 0 ms 296 KB n = 8
18 Correct 0 ms 208 KB n = 8
19 Correct 1 ms 288 KB n = 3
20 Correct 0 ms 208 KB n = 7
21 Correct 1 ms 288 KB n = 8
22 Correct 0 ms 208 KB n = 8
23 Correct 0 ms 208 KB n = 8
24 Correct 0 ms 208 KB n = 8
25 Correct 0 ms 208 KB n = 8
26 Correct 0 ms 208 KB n = 8
27 Correct 1 ms 208 KB n = 8
28 Correct 0 ms 208 KB n = 8
29 Correct 1 ms 296 KB n = 16
30 Correct 0 ms 208 KB n = 16
31 Correct 0 ms 208 KB n = 16
32 Correct 0 ms 208 KB n = 16
33 Correct 0 ms 208 KB n = 16
34 Correct 1 ms 208 KB n = 16
35 Correct 0 ms 208 KB n = 16
36 Correct 1 ms 208 KB n = 15
37 Correct 0 ms 208 KB n = 8
38 Correct 0 ms 208 KB n = 16
39 Correct 0 ms 292 KB n = 16
40 Correct 0 ms 208 KB n = 9
41 Correct 0 ms 208 KB n = 16
42 Correct 0 ms 208 KB n = 16
43 Correct 0 ms 208 KB n = 16
44 Correct 0 ms 208 KB n = 9
45 Correct 0 ms 208 KB n = 15
46 Correct 0 ms 208 KB n = 16
47 Correct 0 ms 208 KB n = 16
48 Correct 0 ms 208 KB n = 16
49 Correct 104 ms 14604 KB n = 199999
50 Correct 104 ms 14616 KB n = 199991
51 Correct 100 ms 14628 KB n = 199993
52 Correct 73 ms 11812 KB n = 152076
53 Correct 49 ms 7132 KB n = 93249
54 Correct 92 ms 13464 KB n = 199910
55 Correct 99 ms 13852 KB n = 199999
56 Correct 94 ms 13464 KB n = 199997
57 Correct 93 ms 12948 KB n = 171294
58 Correct 70 ms 11596 KB n = 140872
59 Correct 99 ms 13464 KB n = 199886
60 Correct 100 ms 13984 KB n = 199996
61 Correct 98 ms 13608 KB n = 200000
62 Correct 110 ms 17364 KB n = 199998
63 Correct 117 ms 16932 KB n = 200000
64 Correct 117 ms 17164 KB n = 199998
65 Correct 87 ms 16304 KB n = 200000
66 Correct 89 ms 14140 KB n = 190000
67 Correct 81 ms 14440 KB n = 177777
68 Correct 51 ms 7436 KB n = 100000
69 Correct 95 ms 14628 KB n = 200000
70 Correct 129 ms 17104 KB n = 200000
71 Correct 123 ms 17156 KB n = 200000
72 Correct 114 ms 14648 KB n = 200000
73 Correct 102 ms 14616 KB n = 200000
74 Correct 101 ms 14540 KB n = 200000
75 Correct 85 ms 14632 KB n = 200000
76 Correct 92 ms 14628 KB n = 200000
77 Correct 100 ms 14668 KB n = 200000
78 Correct 116 ms 17072 KB n = 200000
79 Correct 105 ms 13620 KB n = 184307
80 Correct 36 ms 6304 KB n = 76040
81 Correct 92 ms 13472 KB n = 199981
82 Correct 111 ms 13980 KB n = 199994
83 Correct 108 ms 13604 KB n = 199996
84 Correct 111 ms 17432 KB n = 199998
85 Correct 115 ms 16932 KB n = 200000
86 Correct 129 ms 17068 KB n = 199998
87 Correct 112 ms 16196 KB n = 200000
88 Correct 132 ms 14616 KB n = 200000
89 Correct 96 ms 16292 KB n = 200000
90 Correct 102 ms 14624 KB n = 200000
91 Correct 150 ms 17188 KB n = 200000
92 Correct 149 ms 17172 KB n = 200000