oj.uz

Submission #595278

# Submission time Handle Problem Language Result Execution time Memory
595278 2022-07-13T14:13:45 Z Lucpp Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 942 ms 74732 KB 
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> par;
void init(int n){
    par.resize(n);
    for(int i = 0; i < n; i++) par[i] = i;
}
int find(int i){
    if(par[i] == i) return i;
    else return par[i] = find(par[i]);
}
void merge(int a, int b){
    a = find(a), b = find(b);
    par[a] = b;
}

vector<vector<int>> g;
vector<int> comp;
int dfs_cnt = 0;

void dfs(int u){
    comp[u] = dfs_cnt;
    for(int v : g[u]){
        if(comp[v] == -1) dfs(v);
    }
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    s.push_back(int(1e9+1));
    t.push_back(1);
    int n = (int)s.size();
    vector<pair<int, int>> v;
    vector<pair<int, int>> edges;
    for(int i = 0; i < n; i++){
        v.emplace_back(s[i], 1);
        v.emplace_back(t[i], -1);
        edges.emplace_back(s[i], t[i]);
    }
    sort(v.begin(), v.end());
    int last = 1;
    int sum = 0;
    ll ans = 0;
    for(auto [p, change] : v){
        if(p != last){
            if(sum != 0) edges.emplace_back(last, p), edges.emplace_back(p, last);
            ans += (ll)max(0, sum)*(p-last);
            last = p;
        }
        sum += change;
    }
    set<int> nodes;
    for(auto [u, v] : edges) nodes.insert(u), nodes.insert(v);
    vector<int> vnode(nodes.begin(), nodes.end());
    n = (int)nodes.size();
    g.resize(n);
    for(auto [u, v] : edges){
        int a = int(lower_bound(vnode.begin(), vnode.end(), u)-vnode.begin());
        int b = int(lower_bound(vnode.begin(), vnode.end(), v)-vnode.begin());
        g[a].push_back(b);
    }
    comp.resize(n, -1);
    for(int i = 0; i < n; i++){
        if(comp[i] == -1) dfs(i), dfs_cnt++;
    }
    vector<tuple<int, int, int>> ed;
    for(int i = 1; i < n; i++){
        if(comp[i] != comp[i-1]){
            ed.emplace_back(vnode[i]-vnode[i-1], comp[i], comp[i-1]);
        }
    }
    sort(ed.begin(), ed.end());
    init(dfs_cnt);
    for(auto [c, a, b] : ed){
        if(find(a) != find(b)){
            ans += c;
            merge(a, b);
        }
    }
    return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 0 ms 212 KB n = 2
3 Correct 2 ms 212 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 1 ms 212 KB n = 2
6 Correct 1 ms 212 KB n = 2
7 Correct 0 ms 212 KB n = 3
8 Correct 1 ms 212 KB n = 3
9 Correct 0 ms 212 KB n = 3
10 Correct 1 ms 300 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 292 KB n = 8
13 Correct 1 ms 300 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8
16 Correct 1 ms 296 KB n = 8
17 Correct 3 ms 212 KB n = 8
18 Correct 1 ms 212 KB n = 8
19 Correct 3 ms 212 KB n = 3
20 Correct 1 ms 212 KB n = 7
21 Correct 1 ms 212 KB n = 8
22 Correct 1 ms 212 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 1 ms 256 KB n = 8
25 Correct 1 ms 212 KB n = 8
26 Correct 1 ms 296 KB n = 8
27 Correct 1 ms 300 KB n = 8
28 Correct 0 ms 212 KB n = 8
29 Correct 1 ms 212 KB n = 16
30 Correct 1 ms 300 KB n = 16
31 Correct 1 ms 212 KB n = 16
32 Correct 1 ms 212 KB n = 16
33 Correct 1 ms 300 KB n = 16
34 Correct 1 ms 212 KB n = 16
35 Correct 1 ms 212 KB n = 16
36 Correct 1 ms 296 KB n = 15
37 Correct 1 ms 296 KB n = 8
38 Correct 1 ms 212 KB n = 16
39 Correct 3 ms 296 KB n = 16
40 Correct 1 ms 212 KB n = 9
41 Correct 1 ms 212 KB n = 16
42 Correct 1 ms 300 KB n = 16
43 Correct 1 ms 212 KB n = 16
44 Correct 0 ms 300 KB n = 9
45 Correct 1 ms 340 KB n = 15
46 Correct 1 ms 212 KB n = 16
47 Correct 1 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 887 ms 70952 KB n = 199999
2 Correct 942 ms 67092 KB n = 199991
3 Correct 904 ms 71908 KB n = 199993
4 Correct 647 ms 50900 KB n = 152076
5 Correct 306 ms 32300 KB n = 93249
6 Correct 691 ms 56092 KB n = 199910
7 Correct 763 ms 66440 KB n = 199999
8 Correct 630 ms 57620 KB n = 199997
9 Correct 831 ms 56872 KB n = 171294
10 Correct 607 ms 48256 KB n = 140872
11 Correct 718 ms 56728 KB n = 199886
12 Correct 767 ms 66576 KB n = 199996
13 Correct 665 ms 59340 KB n = 200000
14 Correct 610 ms 68040 KB n = 199998
15 Correct 660 ms 65276 KB n = 200000
16 Correct 772 ms 66928 KB n = 199998
17 Correct 760 ms 68496 KB n = 200000
18 Correct 711 ms 67796 KB n = 190000
19 Correct 664 ms 66372 KB n = 177777
20 Correct 309 ms 34396 KB n = 100000
21 Correct 792 ms 68640 KB n = 200000
22 Correct 790 ms 64340 KB n = 200000
23 Correct 835 ms 71516 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 0 ms 212 KB n = 2
3 Correct 2 ms 212 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 1 ms 212 KB n = 2
6 Correct 1 ms 212 KB n = 2
7 Correct 0 ms 212 KB n = 3
8 Correct 1 ms 212 KB n = 3
9 Correct 0 ms 212 KB n = 3
10 Correct 1 ms 300 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 292 KB n = 8
13 Correct 1 ms 300 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8
16 Correct 1 ms 296 KB n = 8
17 Correct 3 ms 212 KB n = 8
18 Correct 1 ms 212 KB n = 8
19 Correct 3 ms 212 KB n = 3
20 Correct 1 ms 212 KB n = 7
21 Correct 1 ms 212 KB n = 8
22 Correct 1 ms 212 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 1 ms 256 KB n = 8
25 Correct 1 ms 212 KB n = 8
26 Correct 1 ms 296 KB n = 8
27 Correct 1 ms 300 KB n = 8
28 Correct 0 ms 212 KB n = 8
29 Correct 1 ms 212 KB n = 16
30 Correct 1 ms 300 KB n = 16
31 Correct 1 ms 212 KB n = 16
32 Correct 1 ms 212 KB n = 16
33 Correct 1 ms 300 KB n = 16
34 Correct 1 ms 212 KB n = 16
35 Correct 1 ms 212 KB n = 16
36 Correct 1 ms 296 KB n = 15
37 Correct 1 ms 296 KB n = 8
38 Correct 1 ms 212 KB n = 16
39 Correct 3 ms 296 KB n = 16
40 Correct 1 ms 212 KB n = 9
41 Correct 1 ms 212 KB n = 16
42 Correct 1 ms 300 KB n = 16
43 Correct 1 ms 212 KB n = 16
44 Correct 0 ms 300 KB n = 9
45 Correct 1 ms 340 KB n = 15
46 Correct 1 ms 212 KB n = 16
47 Correct 1 ms 212 KB n = 16
48 Correct 1 ms 212 KB n = 16
49 Correct 887 ms 70952 KB n = 199999
50 Correct 942 ms 67092 KB n = 199991
51 Correct 904 ms 71908 KB n = 199993
52 Correct 647 ms 50900 KB n = 152076
53 Correct 306 ms 32300 KB n = 93249
54 Correct 691 ms 56092 KB n = 199910
55 Correct 763 ms 66440 KB n = 199999
56 Correct 630 ms 57620 KB n = 199997
57 Correct 831 ms 56872 KB n = 171294
58 Correct 607 ms 48256 KB n = 140872
59 Correct 718 ms 56728 KB n = 199886
60 Correct 767 ms 66576 KB n = 199996
61 Correct 665 ms 59340 KB n = 200000
62 Correct 610 ms 68040 KB n = 199998
63 Correct 660 ms 65276 KB n = 200000
64 Correct 772 ms 66928 KB n = 199998
65 Correct 760 ms 68496 KB n = 200000
66 Correct 711 ms 67796 KB n = 190000
67 Correct 664 ms 66372 KB n = 177777
68 Correct 309 ms 34396 KB n = 100000
69 Correct 792 ms 68640 KB n = 200000
70 Correct 790 ms 64340 KB n = 200000
71 Correct 835 ms 71516 KB n = 200000
72 Correct 839 ms 74628 KB n = 200000
73 Correct 865 ms 69364 KB n = 200000
74 Correct 892 ms 72940 KB n = 200000
75 Correct 758 ms 74632 KB n = 200000
76 Correct 809 ms 74732 KB n = 200000
77 Correct 452 ms 43328 KB n = 200000
78 Correct 389 ms 39296 KB n = 200000
79 Correct 803 ms 62144 KB n = 184307
80 Correct 244 ms 26444 KB n = 76040
81 Correct 646 ms 56704 KB n = 199981
82 Correct 705 ms 66412 KB n = 199994
83 Correct 619 ms 59364 KB n = 199996
84 Correct 593 ms 68000 KB n = 199998
85 Correct 590 ms 65308 KB n = 200000
86 Correct 623 ms 66832 KB n = 199998
87 Correct 703 ms 68244 KB n = 200000
88 Correct 754 ms 71444 KB n = 200000
89 Correct 694 ms 74536 KB n = 200000
90 Correct 739 ms 68652 KB n = 200000
91 Correct 709 ms 64392 KB n = 200000
92 Correct 753 ms 71540 KB n = 200000