oj.uz

답안 #266663

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
266663 2020-08-15T12:04:59 Z sealnot123 Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 381 ms 42212 KB 
#include "railroad.h"
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define ROF(i, a, b) for(int i=(a); i>=(b); --i)
#define make_unique(a) sort(all((a))), (a).resize(unique(all((a)))-(a).begin())

using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
typedef double DD;
typedef long double LD;
typedef pair<LL,LL> PLL;
typedef pair<DD,DD> PDD;
typedef vector<int> VI;
typedef vector<LL> VL;

const int N = 400004;
int n;
LL plan_roller_coaster(VI s, VI t) {
    int n = SZ(s);
    vector<int> cmp;
    FOR(i, 0, n-1) cmp.pb(s[i]), cmp.pb(t[i]);
    cmp.pb(0); cmp.pb(1e9+2);
    make_unique(cmp);
    FOR(i, 0, n-1){
        s[i] = lower_bound(all(cmp), s[i])-cmp.begin();
        t[i] = lower_bound(all(cmp), t[i])-cmp.begin();
    }
    LL ans = 0;
    int m = SZ(cmp);
    vector<int> dp(m);
    vector<VI> g(m);
    FOR(i, 0, n-1){ 
        g[s[i]].pb(t[i]);
        dp[s[i]]++; dp[t[i]]--;
        //printf("(%d, %d)\n",s[i],t[i]);
    }
    FOR(i, 0, m-2){
        if(i != 0) dp[i] += dp[i-1];
        //printf("%d ",dp[i]);
        if(dp[i] > 1) ans += (dp[i]-1)*1ll*(cmp[i+1]-cmp[i]), g[i+1].pb(i);
        if(dp[i] < 1) g[i].pb(i+1);
    }
    //puts("");
    //printf("%lld\n",ans);
    // mst lets gooo
    queue<int> bfs;
    vector<int> comp(m);
    int cnt = 0;
    FOR(i, 0, m-1){
        if(comp[i]) continue;
        ++cnt;
        comp[i] = cnt;
        bfs.push(i);
        while(!bfs.empty()){
            int u = bfs.front();
            bfs.pop();
            for(int e : g[u]){
                if(comp[e]) continue;
                comp[e] = cnt;
                bfs.push(e);
            }
        }
    }
    vector< pair<int,PII> > edges; // for mst
    vector<int> dsu(cnt+1);
    FOR(i, 1, cnt) dsu[i] = i;
    function<int(int)> find = [&](int i){
        //printf("==%d %d\n",dsu[i],i);
        if(dsu[i] == i) return i;
        return dsu[i] = find(dsu[i]);
    };
    FOR(i, 1, m-2){
        //printf("[%d]\n",comp[i]);
        if(comp[i-1] != comp[i]){
            edges.pb({cmp[i]-cmp[i-1], PII(comp[i-1], comp[i])});
        }
        if(comp[i] != comp[i+1]){
            edges.pb({cmp[i+1]-cmp[i], PII(comp[i+1], comp[i])});
        }
    }
    sort(all(edges));
    for(auto &f : edges){
        LL cost = f.x;
        int a, b;
        tie(a, b) = f.y;
        if(find(a) != find(b)){
            ans += cost;
            dsu[find(a)] = find(b);
        }
    }
    return ans;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB n = 2
2 Correct 0 ms 256 KB n = 2
3 Correct 0 ms 256 KB n = 2
4 Correct 0 ms 256 KB n = 2
5 Correct 1 ms 384 KB n = 2
6 Correct 1 ms 256 KB n = 2
7 Correct 1 ms 256 KB n = 3
8 Correct 1 ms 256 KB n = 3
9 Correct 1 ms 256 KB n = 3
10 Correct 1 ms 256 KB n = 8
11 Correct 1 ms 256 KB n = 8
12 Correct 1 ms 256 KB n = 8
13 Correct 1 ms 384 KB n = 8
14 Correct 1 ms 256 KB n = 8
15 Correct 1 ms 256 KB n = 8
16 Correct 1 ms 256 KB n = 8
17 Correct 1 ms 256 KB n = 8
18 Correct 1 ms 256 KB n = 8
19 Correct 1 ms 256 KB n = 3
20 Correct 1 ms 256 KB n = 7
21 Correct 1 ms 256 KB n = 8
22 Correct 0 ms 256 KB n = 8
23 Correct 1 ms 256 KB n = 8
24 Correct 0 ms 384 KB n = 8
25 Correct 1 ms 256 KB n = 8

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB n = 2
2 Correct 0 ms 256 KB n = 2
3 Correct 0 ms 256 KB n = 2
4 Correct 0 ms 256 KB n = 2
5 Correct 1 ms 384 KB n = 2
6 Correct 1 ms 256 KB n = 2
7 Correct 1 ms 256 KB n = 3
8 Correct 1 ms 256 KB n = 3
9 Correct 1 ms 256 KB n = 3
10 Correct 1 ms 256 KB n = 8
11 Correct 1 ms 256 KB n = 8
12 Correct 1 ms 256 KB n = 8
13 Correct 1 ms 384 KB n = 8
14 Correct 1 ms 256 KB n = 8
15 Correct 1 ms 256 KB n = 8
16 Correct 1 ms 256 KB n = 8
17 Correct 1 ms 256 KB n = 8
18 Correct 1 ms 256 KB n = 8
19 Correct 1 ms 256 KB n = 3
20 Correct 1 ms 256 KB n = 7
21 Correct 1 ms 256 KB n = 8
22 Correct 0 ms 256 KB n = 8
23 Correct 1 ms 256 KB n = 8
24 Correct 0 ms 384 KB n = 8
25 Correct 1 ms 256 KB n = 8
26 Correct 1 ms 256 KB n = 8
27 Correct 1 ms 256 KB n = 8
28 Correct 1 ms 256 KB n = 8
29 Correct 1 ms 384 KB n = 16
30 Correct 1 ms 256 KB n = 16
31 Correct 1 ms 256 KB n = 16
32 Correct 0 ms 256 KB n = 16
33 Correct 1 ms 256 KB n = 16
34 Correct 0 ms 256 KB n = 16
35 Correct 0 ms 256 KB n = 16
36 Correct 0 ms 256 KB n = 15
37 Correct 0 ms 256 KB n = 8
38 Correct 1 ms 256 KB n = 16
39 Correct 0 ms 256 KB n = 16
40 Correct 0 ms 256 KB n = 9
41 Correct 0 ms 256 KB n = 16
42 Correct 0 ms 256 KB n = 16
43 Correct 0 ms 256 KB n = 16
44 Correct 0 ms 256 KB n = 9
45 Correct 1 ms 256 KB n = 15
46 Correct 0 ms 256 KB n = 16
47 Correct 0 ms 256 KB n = 16
48 Correct 1 ms 256 KB n = 16

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 300 ms 33896 KB n = 199999
2 Correct 355 ms 34280 KB n = 199991
3 Correct 303 ms 33900 KB n = 199993
4 Correct 242 ms 25704 KB n = 152076
5 Correct 135 ms 16108 KB n = 93249
6 Correct 289 ms 28264 KB n = 199910
7 Correct 293 ms 32744 KB n = 199999
8 Correct 265 ms 28404 KB n = 199997
9 Correct 291 ms 29160 KB n = 171294
10 Correct 257 ms 24040 KB n = 140872
11 Correct 294 ms 28648 KB n = 199886
12 Correct 320 ms 33000 KB n = 199996
13 Correct 299 ms 29544 KB n = 200000
14 Correct 334 ms 35560 KB n = 199998
15 Correct 307 ms 35048 KB n = 200000
16 Correct 311 ms 36176 KB n = 199998
17 Correct 312 ms 33896 KB n = 200000
18 Correct 325 ms 32360 KB n = 190000
19 Correct 239 ms 30184 KB n = 177777
20 Correct 138 ms 17132 KB n = 100000
21 Correct 333 ms 34152 KB n = 200000
22 Correct 381 ms 42084 KB n = 200000
23 Correct 332 ms 34024 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB n = 2
2 Correct 0 ms 256 KB n = 2
3 Correct 0 ms 256 KB n = 2
4 Correct 0 ms 256 KB n = 2
5 Correct 1 ms 384 KB n = 2
6 Correct 1 ms 256 KB n = 2
7 Correct 1 ms 256 KB n = 3
8 Correct 1 ms 256 KB n = 3
9 Correct 1 ms 256 KB n = 3
10 Correct 1 ms 256 KB n = 8
11 Correct 1 ms 256 KB n = 8
12 Correct 1 ms 256 KB n = 8
13 Correct 1 ms 384 KB n = 8
14 Correct 1 ms 256 KB n = 8
15 Correct 1 ms 256 KB n = 8
16 Correct 1 ms 256 KB n = 8
17 Correct 1 ms 256 KB n = 8
18 Correct 1 ms 256 KB n = 8
19 Correct 1 ms 256 KB n = 3
20 Correct 1 ms 256 KB n = 7
21 Correct 1 ms 256 KB n = 8
22 Correct 0 ms 256 KB n = 8
23 Correct 1 ms 256 KB n = 8
24 Correct 0 ms 384 KB n = 8
25 Correct 1 ms 256 KB n = 8
26 Correct 1 ms 256 KB n = 8
27 Correct 1 ms 256 KB n = 8
28 Correct 1 ms 256 KB n = 8
29 Correct 1 ms 384 KB n = 16
30 Correct 1 ms 256 KB n = 16
31 Correct 1 ms 256 KB n = 16
32 Correct 0 ms 256 KB n = 16
33 Correct 1 ms 256 KB n = 16
34 Correct 0 ms 256 KB n = 16
35 Correct 0 ms 256 KB n = 16
36 Correct 0 ms 256 KB n = 15
37 Correct 0 ms 256 KB n = 8
38 Correct 1 ms 256 KB n = 16
39 Correct 0 ms 256 KB n = 16
40 Correct 0 ms 256 KB n = 9
41 Correct 0 ms 256 KB n = 16
42 Correct 0 ms 256 KB n = 16
43 Correct 0 ms 256 KB n = 16
44 Correct 0 ms 256 KB n = 9
45 Correct 1 ms 256 KB n = 15
46 Correct 0 ms 256 KB n = 16
47 Correct 0 ms 256 KB n = 16
48 Correct 1 ms 256 KB n = 16
49 Correct 300 ms 33896 KB n = 199999
50 Correct 355 ms 34280 KB n = 199991
51 Correct 303 ms 33900 KB n = 199993
52 Correct 242 ms 25704 KB n = 152076
53 Correct 135 ms 16108 KB n = 93249
54 Correct 289 ms 28264 KB n = 199910
55 Correct 293 ms 32744 KB n = 199999
56 Correct 265 ms 28404 KB n = 199997
57 Correct 291 ms 29160 KB n = 171294
58 Correct 257 ms 24040 KB n = 140872
59 Correct 294 ms 28648 KB n = 199886
60 Correct 320 ms 33000 KB n = 199996
61 Correct 299 ms 29544 KB n = 200000
62 Correct 334 ms 35560 KB n = 199998
63 Correct 307 ms 35048 KB n = 200000
64 Correct 311 ms 36176 KB n = 199998
65 Correct 312 ms 33896 KB n = 200000
66 Correct 325 ms 32360 KB n = 190000
67 Correct 239 ms 30184 KB n = 177777
68 Correct 138 ms 17132 KB n = 100000
69 Correct 333 ms 34152 KB n = 200000
70 Correct 381 ms 42084 KB n = 200000
71 Correct 332 ms 34024 KB n = 200000
72 Correct 292 ms 33940 KB n = 200000
73 Correct 349 ms 34076 KB n = 200000
74 Correct 293 ms 34024 KB n = 200000
75 Correct 274 ms 34152 KB n = 200000
76 Correct 281 ms 33924 KB n = 200000
77 Correct 233 ms 21480 KB n = 200000
78 Correct 285 ms 29924 KB n = 200000
79 Correct 317 ms 31256 KB n = 184307
80 Correct 106 ms 13164 KB n = 76040
81 Correct 289 ms 28688 KB n = 199981
82 Correct 305 ms 33000 KB n = 199994
83 Correct 281 ms 29532 KB n = 199996
84 Correct 295 ms 35620 KB n = 199998
85 Correct 292 ms 35176 KB n = 200000
86 Correct 331 ms 36228 KB n = 199998
87 Correct 307 ms 34028 KB n = 200000
88 Correct 312 ms 34024 KB n = 200000
89 Correct 293 ms 34024 KB n = 200000
90 Correct 351 ms 34152 KB n = 200000
91 Correct 370 ms 42212 KB n = 200000
92 Correct 328 ms 34076 KB n = 200000