oj.uz

Submission #610526

# Submission time Handle Problem Language Result Execution time Memory
610526 2022-07-28T09:17:17 Z alirezasamimi100 Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 278 ms 25100 KB 
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using pll = pair<ll,ll>;
#define pb push_back
#define F first
#define S second

vector<ll> cp,ps,p;
vector<pll> vec;
int n;
ll ans;

ll gp(ll x){
    return p[x]==-1?x:p[x]=gp(p[x]);
}

bool uni(ll v, ll u){
    v=gp(v);
    u=gp(u);
    if(v==u) return false;
    p[u]=v;
    return true;
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    s.pb(1e9+10);
    t.pb(1);
    for(int i=0; i<(int)s.size(); i++){
        cp.pb(s[i]);
        cp.pb(t[i]);
    }
    sort(cp.begin(),cp.end());
    cp.resize(unique(cp.begin(),cp.end())-cp.begin());
    n=cp.size();
    ps.resize(n);
    p.resize(n,-1);
    for(int i=0; i<(int)s.size(); i++){
        s[i]=lower_bound(cp.begin(),cp.end(),s[i])-cp.begin();
        t[i]=lower_bound(cp.begin(),cp.end(),t[i])-cp.begin();
        uni(s[i],t[i]);
        ps[s[i]]++;
        ps[t[i]]--;
    }
    for(int i=1; i<n; i++) ps[i]+=ps[i-1];
    for(int i=0; i<n-1; i++){
        if(ps[i]){
            uni(i,i+1);
            if(ps[i]>0) ans+=ps[i]*(cp[i+1]-cp[i]);
        }
        vec.pb({cp[i+1]-cp[i],i});
    }
    sort(vec.begin(),vec.end());
    for(auto [w,i] : vec) if(uni(i,i+1)) ans+=w;
    return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 212 KB n = 2
4 Correct 0 ms 212 KB n = 2
5 Correct 1 ms 212 KB n = 2
6 Correct 0 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 300 KB n = 3
10 Correct 1 ms 296 KB n = 8
11 Correct 0 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 0 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8
16 Correct 0 ms 212 KB n = 8
17 Correct 0 ms 212 KB n = 8
18 Correct 1 ms 296 KB n = 8
19 Correct 1 ms 296 KB n = 3
20 Correct 1 ms 304 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 212 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 300 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 212 KB n = 2
4 Correct 0 ms 212 KB n = 2
5 Correct 1 ms 212 KB n = 2
6 Correct 0 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 300 KB n = 3
10 Correct 1 ms 296 KB n = 8
11 Correct 0 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 0 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8
16 Correct 0 ms 212 KB n = 8
17 Correct 0 ms 212 KB n = 8
18 Correct 1 ms 296 KB n = 8
19 Correct 1 ms 296 KB n = 3
20 Correct 1 ms 304 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 212 KB n = 8
25 Correct 1 ms 212 KB n = 8
26 Correct 0 ms 212 KB n = 8
27 Correct 0 ms 212 KB n = 8
28 Correct 0 ms 300 KB n = 8
29 Correct 1 ms 212 KB n = 16
30 Correct 0 ms 212 KB n = 16
31 Correct 1 ms 212 KB n = 16
32 Correct 0 ms 300 KB n = 16
33 Correct 1 ms 300 KB n = 16
34 Correct 0 ms 212 KB n = 16
35 Correct 1 ms 212 KB n = 16
36 Correct 1 ms 300 KB n = 15
37 Correct 1 ms 212 KB n = 8
38 Correct 1 ms 212 KB n = 16
39 Correct 1 ms 212 KB n = 16
40 Correct 1 ms 212 KB n = 9
41 Correct 1 ms 212 KB n = 16
42 Correct 1 ms 212 KB n = 16
43 Correct 1 ms 212 KB n = 16
44 Correct 1 ms 300 KB n = 9
45 Correct 1 ms 300 KB n = 15
46 Correct 1 ms 212 KB n = 16
47 Correct 0 ms 300 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 228 ms 24664 KB n = 199999
2 Correct 259 ms 24976 KB n = 199991
3 Correct 224 ms 25032 KB n = 199993
4 Correct 170 ms 20784 KB n = 152076
5 Correct 100 ms 12136 KB n = 93249
6 Correct 196 ms 22672 KB n = 199910
7 Correct 185 ms 24104 KB n = 199999
8 Correct 210 ms 22928 KB n = 199997
9 Correct 180 ms 22560 KB n = 171294
10 Correct 142 ms 20124 KB n = 140872
11 Correct 197 ms 22860 KB n = 199886
12 Correct 204 ms 24212 KB n = 199996
13 Correct 220 ms 23164 KB n = 200000
14 Correct 219 ms 24076 KB n = 199998
15 Correct 214 ms 23956 KB n = 200000
16 Correct 208 ms 24524 KB n = 199998
17 Correct 201 ms 25028 KB n = 200000
18 Correct 231 ms 24144 KB n = 190000
19 Correct 173 ms 23192 KB n = 177777
20 Correct 96 ms 12696 KB n = 100000
21 Correct 278 ms 24976 KB n = 200000
22 Correct 205 ms 25040 KB n = 200000
23 Correct 204 ms 25040 KB n = 200000

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 212 KB n = 2
4 Correct 0 ms 212 KB n = 2
5 Correct 1 ms 212 KB n = 2
6 Correct 0 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 300 KB n = 3
10 Correct 1 ms 296 KB n = 8
11 Correct 0 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 0 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8
16 Correct 0 ms 212 KB n = 8
17 Correct 0 ms 212 KB n = 8
18 Correct 1 ms 296 KB n = 8
19 Correct 1 ms 296 KB n = 3
20 Correct 1 ms 304 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 212 KB n = 8
25 Correct 1 ms 212 KB n = 8
26 Correct 0 ms 212 KB n = 8
27 Correct 0 ms 212 KB n = 8
28 Correct 0 ms 300 KB n = 8
29 Correct 1 ms 212 KB n = 16
30 Correct 0 ms 212 KB n = 16
31 Correct 1 ms 212 KB n = 16
32 Correct 0 ms 300 KB n = 16
33 Correct 1 ms 300 KB n = 16
34 Correct 0 ms 212 KB n = 16
35 Correct 1 ms 212 KB n = 16
36 Correct 1 ms 300 KB n = 15
37 Correct 1 ms 212 KB n = 8
38 Correct 1 ms 212 KB n = 16
39 Correct 1 ms 212 KB n = 16
40 Correct 1 ms 212 KB n = 9
41 Correct 1 ms 212 KB n = 16
42 Correct 1 ms 212 KB n = 16
43 Correct 1 ms 212 KB n = 16
44 Correct 1 ms 300 KB n = 9
45 Correct 1 ms 300 KB n = 15
46 Correct 1 ms 212 KB n = 16
47 Correct 0 ms 300 KB n = 16
48 Correct 1 ms 212 KB n = 16
49 Correct 228 ms 24664 KB n = 199999
50 Correct 259 ms 24976 KB n = 199991
51 Correct 224 ms 25032 KB n = 199993
52 Correct 170 ms 20784 KB n = 152076
53 Correct 100 ms 12136 KB n = 93249
54 Correct 196 ms 22672 KB n = 199910
55 Correct 185 ms 24104 KB n = 199999
56 Correct 210 ms 22928 KB n = 199997
57 Correct 180 ms 22560 KB n = 171294
58 Correct 142 ms 20124 KB n = 140872
59 Correct 197 ms 22860 KB n = 199886
60 Correct 204 ms 24212 KB n = 199996
61 Correct 220 ms 23164 KB n = 200000
62 Correct 219 ms 24076 KB n = 199998
63 Correct 214 ms 23956 KB n = 200000
64 Correct 208 ms 24524 KB n = 199998
65 Correct 201 ms 25028 KB n = 200000
66 Correct 231 ms 24144 KB n = 190000
67 Correct 173 ms 23192 KB n = 177777
68 Correct 96 ms 12696 KB n = 100000
69 Correct 278 ms 24976 KB n = 200000
70 Correct 205 ms 25040 KB n = 200000
71 Correct 204 ms 25040 KB n = 200000
72 Correct 239 ms 25032 KB n = 200000
73 Correct 224 ms 25032 KB n = 200000
74 Correct 210 ms 25100 KB n = 200000
75 Correct 209 ms 25028 KB n = 200000
76 Correct 220 ms 24984 KB n = 200000
77 Correct 157 ms 19676 KB n = 200000
78 Correct 171 ms 19720 KB n = 200000
79 Correct 207 ms 23592 KB n = 184307
80 Correct 73 ms 10720 KB n = 76040
81 Correct 184 ms 22800 KB n = 199981
82 Correct 200 ms 24336 KB n = 199994
83 Correct 204 ms 23180 KB n = 199996
84 Correct 200 ms 24208 KB n = 199998
85 Correct 214 ms 23960 KB n = 200000
86 Correct 243 ms 24520 KB n = 199998
87 Correct 201 ms 24976 KB n = 200000
88 Correct 205 ms 25036 KB n = 200000
89 Correct 198 ms 25028 KB n = 200000
90 Correct 231 ms 25096 KB n = 200000
91 Correct 208 ms 24976 KB n = 200000
92 Correct 216 ms 24996 KB n = 200000