oj.uz

Submission #210625

# Submission time Handle Problem Language Result Execution time Memory
210625 2020-03-17T23:11:19 Z anonymous Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 628 ms 42904 KB 
#include "railroad.h"
#include <map>
#include <set>
#include <utility>
#include <vector>
#include <algorithm>
#include <cassert>
#define MAXN 200005
#define LL long long
using namespace std;
class DSU {
    int Set[MAXN];
public:
    void init(int n) {for(int i=0; i<=n; i++) {Set[i]=i;};}
    int Find(int x) {return(Set[x] == x ? x : Set[x] = Find(Set[x]));}
    void Union(int x, int y) {Set[Find(x)] = Find(y);}
} UF;

multiset<pair<pair<int,int> , bool> > R; // [[val, id], s = true, t = false]
bool active[MAXN];
LL plan_roller_coaster(vector<int> s, vector<int> t) {
    int N = (int) s.size();
    LL ans = 0;
    UF.init(N);
    for (int i=0; i < N; i++) {
        R.insert({{s[i],i}, true});
        R.insert({{t[i],i}, false});
    }
    R.insert({{0, N}, false});
    R.insert({{1<<30, N}, true});
    int up=0, down=0;
    for (auto p: R) {
        if (!active[p.first.second]) {
            if (p.second) {up++;}
            else {down++;}
            active[p.first.second] = true;
        } else {
            if (p.second) {down--;}
            else {up--;}
            active[p.first.second] = false;
        }
        if (down > up && p != *R.rbegin()) {
            //printf("Link up %d %d\n", p.first.first,(*R.upper_bound(p)).first.first);
            UF.Union(p.first.second, (*R.upper_bound(p)).first.second);
        } else if (up > down) {
            assert(p != *R.rbegin());
            //printf("Link down %d %d\n", p.first.first,(*R.upper_bound(p)).first.first);
            ans += ((LL) (*R.upper_bound(p)).first.first - p.first.first)*((LL) up - down);
            UF.Union(p.first.second, (*R.upper_bound(p)).first.second);
        }
    }
    //printf("%d\n", ans);
    vector<pair<int, pair<int,int> > > Edge;
    int prev_id, prev_pos;
    for (auto p: R) {
        if (p == *R.begin()) {
            prev_id = p.first.second, prev_pos = p.first.first;
            continue;
        } else {
            Edge.push_back({p.first.first - prev_pos, {p.first.second, prev_id}});
            prev_id = p.first.second, prev_pos = p.first.first;
        }
    }
    sort(Edge.begin(), Edge.end());
    for (auto e: Edge) {
        if (UF.Find(e.second.first) != UF.Find(e.second.second)) {
            UF.Union(e.second.first, e.second.second);
            ans += e.first;
        }
    }
    return(ans);
}

Compilation message

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:60:43: warning: 'prev_pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
             Edge.push_back({p.first.first - prev_pos, {p.first.second, prev_id}});
                             ~~~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 39744 KB n = 199999
2 Correct 617 ms 39656 KB n = 199991
3 Correct 628 ms 39780 KB n = 199993
4 Correct 427 ms 31496 KB n = 152076
5 Correct 236 ms 18924 KB n = 93249
6 Correct 530 ms 38504 KB n = 199910
7 Correct 488 ms 39400 KB n = 199999
8 Correct 479 ms 39012 KB n = 199997
9 Correct 492 ms 34792 KB n = 171294
10 Correct 402 ms 29928 KB n = 140872
11 Correct 519 ms 38500 KB n = 199886
12 Correct 479 ms 39580 KB n = 199996
13 Correct 468 ms 39140 KB n = 200000
14 Correct 435 ms 40680 KB n = 199998
15 Correct 440 ms 40036 KB n = 200000
16 Correct 455 ms 40172 KB n = 199998
17 Correct 480 ms 42728 KB n = 200000
18 Correct 488 ms 38248 KB n = 190000
19 Correct 412 ms 38760 KB n = 177777
20 Correct 209 ms 20076 KB n = 100000
21 Correct 501 ms 39652 KB n = 200000
22 Correct 517 ms 39656 KB n = 200000
23 Correct 552 ms 39652 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB n = 2
2 Correct 5 ms 256 KB n = 2
3 Correct 5 ms 256 KB n = 2
4 Correct 4 ms 256 KB n = 2
5 Correct 5 ms 256 KB n = 2
6 Correct 5 ms 256 KB n = 2
7 Correct 4 ms 256 KB n = 3
8 Correct 4 ms 256 KB n = 3
9 Correct 7 ms 256 KB n = 3
10 Correct 4 ms 376 KB n = 8
11 Correct 5 ms 256 KB n = 8
12 Correct 5 ms 376 KB n = 8
13 Correct 5 ms 360 KB n = 8
14 Correct 5 ms 256 KB n = 8
15 Correct 5 ms 256 KB n = 8
16 Correct 6 ms 376 KB n = 8
17 Correct 4 ms 256 KB n = 8
18 Correct 5 ms 256 KB n = 8
19 Correct 5 ms 256 KB n = 3
20 Correct 5 ms 256 KB n = 7
21 Correct 4 ms 256 KB n = 8
22 Correct 5 ms 256 KB n = 8
23 Correct 5 ms 256 KB n = 8
24 Correct 5 ms 256 KB n = 8
25 Correct 5 ms 256 KB n = 8
26 Correct 5 ms 256 KB n = 8
27 Correct 5 ms 256 KB n = 8
28 Correct 4 ms 256 KB n = 8
29 Correct 5 ms 256 KB n = 16
30 Correct 4 ms 256 KB n = 16
31 Correct 5 ms 256 KB n = 16
32 Correct 4 ms 256 KB n = 16
33 Correct 5 ms 256 KB n = 16
34 Correct 5 ms 256 KB n = 16
35 Correct 5 ms 256 KB n = 16
36 Correct 5 ms 256 KB n = 15
37 Correct 5 ms 256 KB n = 8
38 Correct 5 ms 376 KB n = 16
39 Correct 5 ms 376 KB n = 16
40 Correct 5 ms 256 KB n = 9
41 Correct 5 ms 256 KB n = 16
42 Correct 5 ms 256 KB n = 16
43 Correct 5 ms 376 KB n = 16
44 Correct 5 ms 376 KB n = 9
45 Correct 5 ms 256 KB n = 15
46 Correct 4 ms 256 KB n = 16
47 Correct 5 ms 256 KB n = 16
48 Correct 5 ms 380 KB n = 16
49 Correct 602 ms 39744 KB n = 199999
50 Correct 617 ms 39656 KB n = 199991
51 Correct 628 ms 39780 KB n = 199993
52 Correct 427 ms 31496 KB n = 152076
53 Correct 236 ms 18924 KB n = 93249
54 Correct 530 ms 38504 KB n = 199910
55 Correct 488 ms 39400 KB n = 199999
56 Correct 479 ms 39012 KB n = 199997
57 Correct 492 ms 34792 KB n = 171294
58 Correct 402 ms 29928 KB n = 140872
59 Correct 519 ms 38500 KB n = 199886
60 Correct 479 ms 39580 KB n = 199996
61 Correct 468 ms 39140 KB n = 200000
62 Correct 435 ms 40680 KB n = 199998
63 Correct 440 ms 40036 KB n = 200000
64 Correct 455 ms 40172 KB n = 199998
65 Correct 480 ms 42728 KB n = 200000
66 Correct 488 ms 38248 KB n = 190000
67 Correct 412 ms 38760 KB n = 177777
68 Correct 209 ms 20076 KB n = 100000
69 Correct 501 ms 39652 KB n = 200000
70 Correct 517 ms 39656 KB n = 200000
71 Correct 552 ms 39652 KB n = 200000
72 Correct 588 ms 39656 KB n = 200000
73 Correct 598 ms 39656 KB n = 200000
74 Correct 610 ms 39652 KB n = 200000
75 Correct 505 ms 39644 KB n = 200000
76 Correct 481 ms 39652 KB n = 200000
77 Correct 422 ms 42724 KB n = 200000
78 Correct 398 ms 39652 KB n = 200000
79 Correct 519 ms 36840 KB n = 184307
80 Correct 183 ms 16108 KB n = 76040
81 Correct 519 ms 38500 KB n = 199981
82 Correct 477 ms 39528 KB n = 199994
83 Correct 476 ms 39140 KB n = 199996
84 Correct 457 ms 40680 KB n = 199998
85 Correct 452 ms 40040 KB n = 200000
86 Correct 464 ms 40168 KB n = 199998
87 Correct 508 ms 42904 KB n = 200000
88 Correct 545 ms 40296 KB n = 200000
89 Correct 511 ms 42724 KB n = 200000
90 Correct 515 ms 39652 KB n = 200000
91 Correct 520 ms 39652 KB n = 200000
92 Correct 554 ms 39660 KB n = 200000