oj.uz

답안 #535438

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535438 2022-03-10T09:24:40 Z mario05092929 Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 451 ms 50616 KB 
#include "railroad.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <int,int> pi;
typedef vector <int> vec;
const ll INF = 1e18;
int n,m;
vec s,t;
ll bitdp[1 << 16][16];
int ind[400005],oud[400005],mx;
int c[400005],p[400005];
vec rev;
vector <int> v[400005];
vector <pair<int,pi>> edge;

int Find(int x) {return (x == p[x] ? x : p[x] = Find(p[x]));}

ll dist(int x,int y) {
    return max(0,t[x]-s[y]);
}

void merge(int x,int y) {
    x = Find(x), y = Find(y);
    if(x == y) return;
    p[y] = x;
}

void dfs(int x,int co) {
    if(p[x] != -1) return;
    p[x] = co;
    for(int i : v[x]) dfs(i,co);
}

ll plan_roller_coaster(vec S,vec T) {
    s = S, t = T;
    n = s.size();
    for(int i = 0;i < n;i++) {
        rev.push_back(s[i]);
        rev.push_back(t[i]);
    }
    sort(rev.begin(),rev.end());
    rev.erase(unique(rev.begin(),rev.end()),rev.end());
    m = rev.size();
    for(int i = 0;i < n;i++) {
        s[i] = lower_bound(rev.begin(),rev.end(),s[i])-rev.begin();
        t[i] = lower_bound(rev.begin(),rev.end(),t[i])-rev.begin();
        oud[s[i]]++, ind[t[i]]++;
        v[s[i]].push_back(t[i]);
    }
    ll ans = 0;
    for(int i = 0;i < m-1;i++) {
        int tmp = ind[i]-oud[i];
        if(!i) tmp++;
        if(ind[i] > oud[i]+(i?0:-1)) v[i].push_back(i+1);
        if(ind[i] < oud[i]+(i?0:-1)) ans -= 1LL*(rev[i+1]-rev[i])*tmp, v[i+1].push_back(i);
        oud[i] += tmp;
        ind[i+1] += tmp;
        edge.push_back({rev[i+1]-rev[i],{i,i+1}});
    }
    sort(edge.begin(),edge.end());
    memset(p,-1,sizeof(p));
    for(int i = 0;i < m;i++) dfs(i,i);
    for(auto i : edge) {
        int x = i.y.x, y = i.y.y;
        int cost = i.x;
        if(Find(x) == Find(y)) continue;
        //cout << x << ' ' << y << " : " << cost << '\n';
        merge(x,y);
        ans += cost;
    }

    return ans;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11244 KB n = 2
2 Correct 6 ms 11220 KB n = 2
3 Correct 7 ms 11292 KB n = 2
4 Correct 6 ms 11220 KB n = 2
5 Correct 7 ms 11244 KB n = 2
6 Correct 7 ms 11220 KB n = 2
7 Correct 8 ms 11236 KB n = 3
8 Correct 7 ms 11248 KB n = 3
9 Correct 6 ms 11244 KB n = 3
10 Correct 7 ms 11252 KB n = 8
11 Correct 7 ms 11244 KB n = 8
12 Correct 6 ms 11220 KB n = 8
13 Correct 7 ms 11220 KB n = 8
14 Correct 7 ms 11248 KB n = 8
15 Correct 7 ms 11220 KB n = 8
16 Correct 7 ms 11216 KB n = 8
17 Correct 6 ms 11220 KB n = 8
18 Correct 8 ms 11256 KB n = 8
19 Correct 7 ms 11240 KB n = 3
20 Correct 6 ms 11280 KB n = 7
21 Correct 9 ms 11224 KB n = 8
22 Correct 6 ms 11244 KB n = 8
23 Correct 7 ms 11248 KB n = 8
24 Correct 7 ms 11248 KB n = 8
25 Correct 10 ms 11292 KB n = 8

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11244 KB n = 2
2 Correct 6 ms 11220 KB n = 2
3 Correct 7 ms 11292 KB n = 2
4 Correct 6 ms 11220 KB n = 2
5 Correct 7 ms 11244 KB n = 2
6 Correct 7 ms 11220 KB n = 2
7 Correct 8 ms 11236 KB n = 3
8 Correct 7 ms 11248 KB n = 3
9 Correct 6 ms 11244 KB n = 3
10 Correct 7 ms 11252 KB n = 8
11 Correct 7 ms 11244 KB n = 8
12 Correct 6 ms 11220 KB n = 8
13 Correct 7 ms 11220 KB n = 8
14 Correct 7 ms 11248 KB n = 8
15 Correct 7 ms 11220 KB n = 8
16 Correct 7 ms 11216 KB n = 8
17 Correct 6 ms 11220 KB n = 8
18 Correct 8 ms 11256 KB n = 8
19 Correct 7 ms 11240 KB n = 3
20 Correct 6 ms 11280 KB n = 7
21 Correct 9 ms 11224 KB n = 8
22 Correct 6 ms 11244 KB n = 8
23 Correct 7 ms 11248 KB n = 8
24 Correct 7 ms 11248 KB n = 8
25 Correct 10 ms 11292 KB n = 8
26 Correct 6 ms 11244 KB n = 8
27 Correct 7 ms 11220 KB n = 8
28 Correct 6 ms 11220 KB n = 8
29 Correct 7 ms 11220 KB n = 16
30 Correct 6 ms 11220 KB n = 16
31 Correct 7 ms 11220 KB n = 16
32 Correct 8 ms 11248 KB n = 16
33 Correct 8 ms 11208 KB n = 16
34 Correct 7 ms 11220 KB n = 16
35 Correct 9 ms 11236 KB n = 16
36 Correct 7 ms 11244 KB n = 15
37 Correct 6 ms 11244 KB n = 8
38 Correct 7 ms 11176 KB n = 16
39 Correct 7 ms 11220 KB n = 16
40 Correct 11 ms 11220 KB n = 9
41 Correct 11 ms 11248 KB n = 16
42 Correct 15 ms 11220 KB n = 16
43 Correct 6 ms 11220 KB n = 16
44 Correct 8 ms 11244 KB n = 9
45 Correct 9 ms 11188 KB n = 15
46 Correct 7 ms 11220 KB n = 16
47 Correct 6 ms 11252 KB n = 16
48 Correct 8 ms 11248 KB n = 16

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 358 ms 50464 KB n = 199999
2 Correct 446 ms 45464 KB n = 199991
3 Correct 377 ms 50252 KB n = 199993
4 Correct 304 ms 36676 KB n = 152076
5 Correct 171 ms 27196 KB n = 93249
6 Correct 320 ms 39212 KB n = 199910
7 Correct 347 ms 44672 KB n = 199999
8 Correct 359 ms 40584 KB n = 199997
9 Correct 357 ms 40448 KB n = 171294
10 Correct 291 ms 35068 KB n = 140872
11 Correct 359 ms 39436 KB n = 199886
12 Correct 360 ms 44768 KB n = 199996
13 Correct 331 ms 41612 KB n = 200000
14 Correct 370 ms 46476 KB n = 199998
15 Correct 365 ms 44896 KB n = 200000
16 Correct 364 ms 45636 KB n = 199998
17 Correct 356 ms 46104 KB n = 200000
18 Correct 366 ms 44724 KB n = 190000
19 Correct 323 ms 46128 KB n = 177777
20 Correct 188 ms 28312 KB n = 100000
21 Correct 419 ms 45532 KB n = 200000
22 Correct 377 ms 41668 KB n = 200000
23 Correct 430 ms 50548 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11244 KB n = 2
2 Correct 6 ms 11220 KB n = 2
3 Correct 7 ms 11292 KB n = 2
4 Correct 6 ms 11220 KB n = 2
5 Correct 7 ms 11244 KB n = 2
6 Correct 7 ms 11220 KB n = 2
7 Correct 8 ms 11236 KB n = 3
8 Correct 7 ms 11248 KB n = 3
9 Correct 6 ms 11244 KB n = 3
10 Correct 7 ms 11252 KB n = 8
11 Correct 7 ms 11244 KB n = 8
12 Correct 6 ms 11220 KB n = 8
13 Correct 7 ms 11220 KB n = 8
14 Correct 7 ms 11248 KB n = 8
15 Correct 7 ms 11220 KB n = 8
16 Correct 7 ms 11216 KB n = 8
17 Correct 6 ms 11220 KB n = 8
18 Correct 8 ms 11256 KB n = 8
19 Correct 7 ms 11240 KB n = 3
20 Correct 6 ms 11280 KB n = 7
21 Correct 9 ms 11224 KB n = 8
22 Correct 6 ms 11244 KB n = 8
23 Correct 7 ms 11248 KB n = 8
24 Correct 7 ms 11248 KB n = 8
25 Correct 10 ms 11292 KB n = 8
26 Correct 6 ms 11244 KB n = 8
27 Correct 7 ms 11220 KB n = 8
28 Correct 6 ms 11220 KB n = 8
29 Correct 7 ms 11220 KB n = 16
30 Correct 6 ms 11220 KB n = 16
31 Correct 7 ms 11220 KB n = 16
32 Correct 8 ms 11248 KB n = 16
33 Correct 8 ms 11208 KB n = 16
34 Correct 7 ms 11220 KB n = 16
35 Correct 9 ms 11236 KB n = 16
36 Correct 7 ms 11244 KB n = 15
37 Correct 6 ms 11244 KB n = 8
38 Correct 7 ms 11176 KB n = 16
39 Correct 7 ms 11220 KB n = 16
40 Correct 11 ms 11220 KB n = 9
41 Correct 11 ms 11248 KB n = 16
42 Correct 15 ms 11220 KB n = 16
43 Correct 6 ms 11220 KB n = 16
44 Correct 8 ms 11244 KB n = 9
45 Correct 9 ms 11188 KB n = 15
46 Correct 7 ms 11220 KB n = 16
47 Correct 6 ms 11252 KB n = 16
48 Correct 8 ms 11248 KB n = 16
49 Correct 358 ms 50464 KB n = 199999
50 Correct 446 ms 45464 KB n = 199991
51 Correct 377 ms 50252 KB n = 199993
52 Correct 304 ms 36676 KB n = 152076
53 Correct 171 ms 27196 KB n = 93249
54 Correct 320 ms 39212 KB n = 199910
55 Correct 347 ms 44672 KB n = 199999
56 Correct 359 ms 40584 KB n = 199997
57 Correct 357 ms 40448 KB n = 171294
58 Correct 291 ms 35068 KB n = 140872
59 Correct 359 ms 39436 KB n = 199886
60 Correct 360 ms 44768 KB n = 199996
61 Correct 331 ms 41612 KB n = 200000
62 Correct 370 ms 46476 KB n = 199998
63 Correct 365 ms 44896 KB n = 200000
64 Correct 364 ms 45636 KB n = 199998
65 Correct 356 ms 46104 KB n = 200000
66 Correct 366 ms 44724 KB n = 190000
67 Correct 323 ms 46128 KB n = 177777
68 Correct 188 ms 28312 KB n = 100000
69 Correct 419 ms 45532 KB n = 200000
70 Correct 377 ms 41668 KB n = 200000
71 Correct 430 ms 50548 KB n = 200000
72 Correct 438 ms 50616 KB n = 200000
73 Correct 428 ms 45576 KB n = 200000
74 Correct 451 ms 49312 KB n = 200000
75 Correct 392 ms 50468 KB n = 200000
76 Correct 419 ms 50444 KB n = 200000
77 Correct 343 ms 37504 KB n = 200000
78 Correct 269 ms 33148 KB n = 200000
79 Correct 388 ms 41540 KB n = 184307
80 Correct 145 ms 24296 KB n = 76040
81 Correct 352 ms 39472 KB n = 199981
82 Correct 370 ms 44772 KB n = 199994
83 Correct 353 ms 41488 KB n = 199996
84 Correct 377 ms 46536 KB n = 199998
85 Correct 378 ms 44808 KB n = 200000
86 Correct 395 ms 45660 KB n = 199998
87 Correct 370 ms 46112 KB n = 200000
88 Correct 387 ms 46368 KB n = 200000
89 Correct 361 ms 50452 KB n = 200000
90 Correct 411 ms 45468 KB n = 200000
91 Correct 387 ms 41784 KB n = 200000
92 Correct 368 ms 50528 KB n = 200000