oj.uz

Submission #906809

# Submission time Handle Problem Language Result Execution time Memory
906809 2024-01-15T02:56:31 Z mathnetic Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 543 ms 29584 KB 
#include <bits/stdc++.h>

#include "railroad.h"



using namespace std;



typedef pair<int, int> P;

typedef long long L;



unordered_map<int, int> m;



int f(int x) {

    if (m[x] == 0) m[x] = x;

    return (x == m[x]) ? x : (m[x] = f(m[x]));

}



void u(int x, int y) {

    m[f(x)] = f(y);

}



bool c(P a, P b) {

    return (a.second - a.first) < (b.second - b.first);

}



L plan_roller_coaster(vector<int> s, vector<int> t) {

    L r = 0;

    s.push_back(1e9);

    t.push_back(1);

    int n = s.size();

    vector<P> v, d;



    for (int i = 0; i < n; ++i) {

        u(s[i], t[i]);

        v.emplace_back(s[i], 1);

        v.emplace_back(t[i], -1);

    }



    sort(v.begin(), v.end());

    int b = 0;



    for (int i = 0, j = 0; i < v.size(); i = j) {

        for (; j < v.size() && v[j].first == v[i].first; ++j) {

            b += v[j].second;

        }



        if (!(j >= v.size())) {

            if (b > 0) {

                r += static_cast<L>(b) * (v[j].first - v[i].first);

            }



            if (b == 0) {

                d.emplace_back(v[i].first, v[j].first);

            } else {

                u(v[j].first, v[i].first);

            }

        }

    }



    sort(d.begin(), d.end(), c);



    for (auto i : d) {

        if (f(i.first) != f(i.second)) {

            r += i.second - i.first;

            u(i.first, i.second);

        }

    }



    return r;

}

Compilation message

railroad.cpp: In function 'L plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:79:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 0, j = 0; i < v.size(); i = j) {
      |                            ~~^~~~~~~~~~
railroad.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (; j < v.size() && v[j].first == v[i].first; ++j) {
      |                ~~^~~~~~~~~~
railroad.cpp:89:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         if (!(j >= v.size())) {
      |               ~~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 26076 KB n = 199999
2 Correct 341 ms 26592 KB n = 199991
3 Correct 336 ms 26336 KB n = 199993
4 Correct 191 ms 19136 KB n = 152076
5 Correct 87 ms 12752 KB n = 93249
6 Correct 194 ms 19704 KB n = 199910
7 Correct 313 ms 25572 KB n = 199999
8 Correct 189 ms 20188 KB n = 199997
9 Correct 230 ms 19392 KB n = 171294
10 Correct 242 ms 19224 KB n = 140872
11 Correct 197 ms 19884 KB n = 199886
12 Correct 280 ms 25828 KB n = 199996
13 Correct 207 ms 20708 KB n = 200000
14 Correct 435 ms 29500 KB n = 199998
15 Correct 464 ms 28704 KB n = 200000
16 Correct 487 ms 29084 KB n = 199998
17 Correct 403 ms 25820 KB n = 200000
18 Correct 365 ms 26420 KB n = 190000
19 Correct 280 ms 25492 KB n = 177777
20 Correct 100 ms 12704 KB n = 100000
21 Correct 312 ms 25484 KB n = 200000
22 Correct 534 ms 28604 KB n = 200000
23 Correct 497 ms 28400 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 2
2 Correct 0 ms 348 KB n = 2
3 Correct 0 ms 348 KB n = 2
4 Correct 0 ms 348 KB n = 2
5 Correct 0 ms 348 KB n = 2
6 Correct 0 ms 348 KB n = 2
7 Correct 1 ms 348 KB n = 3
8 Correct 1 ms 348 KB n = 3
9 Correct 0 ms 348 KB n = 3
10 Correct 1 ms 348 KB n = 8
11 Correct 0 ms 348 KB n = 8
12 Correct 0 ms 348 KB n = 8
13 Correct 1 ms 348 KB n = 8
14 Correct 0 ms 348 KB n = 8
15 Correct 1 ms 344 KB n = 8
16 Correct 1 ms 348 KB n = 8
17 Correct 0 ms 348 KB n = 8
18 Correct 0 ms 348 KB n = 8
19 Correct 1 ms 348 KB n = 3
20 Correct 0 ms 348 KB n = 7
21 Correct 1 ms 344 KB n = 8
22 Correct 0 ms 344 KB n = 8
23 Correct 0 ms 344 KB n = 8
24 Correct 1 ms 348 KB n = 8
25 Correct 0 ms 348 KB n = 8
26 Correct 0 ms 348 KB n = 8
27 Correct 1 ms 348 KB n = 8
28 Correct 0 ms 344 KB n = 8
29 Correct 0 ms 348 KB n = 16
30 Correct 1 ms 348 KB n = 16
31 Correct 1 ms 348 KB n = 16
32 Correct 1 ms 344 KB n = 16
33 Correct 1 ms 344 KB n = 16
34 Correct 0 ms 348 KB n = 16
35 Correct 0 ms 348 KB n = 16
36 Correct 1 ms 348 KB n = 15
37 Correct 0 ms 344 KB n = 8
38 Correct 1 ms 348 KB n = 16
39 Correct 0 ms 348 KB n = 16
40 Correct 1 ms 348 KB n = 9
41 Correct 0 ms 348 KB n = 16
42 Correct 0 ms 344 KB n = 16
43 Correct 1 ms 344 KB n = 16
44 Correct 0 ms 348 KB n = 9
45 Correct 1 ms 348 KB n = 15
46 Correct 1 ms 348 KB n = 16
47 Correct 0 ms 348 KB n = 16
48 Correct 1 ms 348 KB n = 16
49 Correct 342 ms 26076 KB n = 199999
50 Correct 341 ms 26592 KB n = 199991
51 Correct 336 ms 26336 KB n = 199993
52 Correct 191 ms 19136 KB n = 152076
53 Correct 87 ms 12752 KB n = 93249
54 Correct 194 ms 19704 KB n = 199910
55 Correct 313 ms 25572 KB n = 199999
56 Correct 189 ms 20188 KB n = 199997
57 Correct 230 ms 19392 KB n = 171294
58 Correct 242 ms 19224 KB n = 140872
59 Correct 197 ms 19884 KB n = 199886
60 Correct 280 ms 25828 KB n = 199996
61 Correct 207 ms 20708 KB n = 200000
62 Correct 435 ms 29500 KB n = 199998
63 Correct 464 ms 28704 KB n = 200000
64 Correct 487 ms 29084 KB n = 199998
65 Correct 403 ms 25820 KB n = 200000
66 Correct 365 ms 26420 KB n = 190000
67 Correct 280 ms 25492 KB n = 177777
68 Correct 100 ms 12704 KB n = 100000
69 Correct 312 ms 25484 KB n = 200000
70 Correct 534 ms 28604 KB n = 200000
71 Correct 497 ms 28400 KB n = 200000
72 Correct 365 ms 25952 KB n = 200000
73 Correct 359 ms 26380 KB n = 200000
74 Correct 355 ms 26172 KB n = 200000
75 Correct 331 ms 25568 KB n = 200000
76 Correct 391 ms 25572 KB n = 200000
77 Correct 133 ms 16564 KB n = 200000
78 Correct 184 ms 19560 KB n = 200000
79 Correct 334 ms 25696 KB n = 184307
80 Correct 74 ms 9168 KB n = 76040
81 Correct 207 ms 20052 KB n = 199981
82 Correct 313 ms 25444 KB n = 199994
83 Correct 219 ms 20940 KB n = 199996
84 Correct 410 ms 28964 KB n = 199998
85 Correct 412 ms 29220 KB n = 200000
86 Correct 451 ms 29584 KB n = 199998
87 Correct 389 ms 25572 KB n = 200000
88 Correct 372 ms 26320 KB n = 200000
89 Correct 356 ms 25444 KB n = 200000
90 Correct 328 ms 25956 KB n = 200000
91 Correct 502 ms 28620 KB n = 200000
92 Correct 543 ms 28452 KB n = 200000