oj.uz

답안 #205350

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
205350 2020-02-28T15:59:55 Z combi1k1 Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 264 ms 18388 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 4e5 + 5;

typedef pair<int,int>   ii;
typedef pair<int,ii>    ed;

int p[N];
int s[N];

int init(int n) {
    iota(p,p + n,0);
    fill(s,s + n,1);
    return  1;
}
int lead(int x) {
    return p[x] == x ? x : p[x] = lead(p[x]);
}
int join(int x,int y)   {
    x = lead(x);
    y = lead(y);

    if (x == y) return  0;
    if (s[x] < s[y])
        swap(x,y);
    p[y] = x;
    s[x] += s[y];

    return  1;
}

int f[N];

ll  plan_roller_coaster(vector<int> s,vector<int> t)    {
    s.pb(1e9);
    t.pb(1);

    int n = s.size();

    vector<int> val;

    for(int i = 0 ; i < n ; ++i)    {
        val.pb(s[i]);
        val.pb(t[i]);
    }

    sort(all(val));
    val.erase(unique(all(val)),val.end());

    init(sz(val));

    for(int i = 0 ; i < n ; ++i)    {
        int l = lower_bound(all(val),s[i]) - val.begin();
        int r = lower_bound(all(val),t[i]) - val.begin();

        f[l]++;
        f[r]--;

        join(l,r);
    }
    ll  ans = 0;
    ll  Sum = 0;

    vector<ed>  E;

    for(int i = 1 ; i < sz(val) ; ++i)  {
        Sum += f[i - 1];

        if (Sum == 0)    E.pb(val[i] - val[i - 1],ii(i - 1,i));
        else    {
            join(i - 1,i);

            if (Sum > 0)
                ans += Sum * (val[i] - val[i - 1]);
        }
    }
    sort(all(E));

    for(ed  e : E)  {
        int w = e.X;
        int u = e.Y.X;
        int v = e.Y.Y;

        if (join(u,v))
            ans += w;
    }
    return  ans;
}

//int main()  {
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//
//    cout << plan_roller_coaster({1,4,5,6},{7,3,8,6}) << endl;
//}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 12884 KB n = 199999
2 Correct 212 ms 14804 KB n = 199991
3 Correct 208 ms 14676 KB n = 199993
4 Correct 149 ms 11084 KB n = 152076
5 Correct 91 ms 7060 KB n = 93249
6 Correct 187 ms 12756 KB n = 199910
7 Correct 193 ms 13780 KB n = 199999
8 Correct 184 ms 12756 KB n = 199997
9 Correct 174 ms 12596 KB n = 171294
10 Correct 137 ms 9764 KB n = 140872
11 Correct 188 ms 12884 KB n = 199886
12 Correct 200 ms 13908 KB n = 199996
13 Correct 193 ms 13140 KB n = 200000
14 Correct 220 ms 17400 KB n = 199998
15 Correct 211 ms 17236 KB n = 200000
16 Correct 227 ms 17752 KB n = 199998
17 Correct 212 ms 14676 KB n = 200000
18 Correct 206 ms 13964 KB n = 190000
19 Correct 187 ms 13188 KB n = 177777
20 Correct 99 ms 7524 KB n = 100000
21 Correct 211 ms 14720 KB n = 200000
22 Correct 257 ms 18312 KB n = 200000
23 Correct 264 ms 18320 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB n = 2
2 Correct 5 ms 376 KB n = 2
3 Correct 5 ms 376 KB n = 2
4 Correct 5 ms 376 KB n = 2
5 Correct 5 ms 368 KB n = 2
6 Correct 5 ms 376 KB n = 2
7 Correct 5 ms 376 KB n = 3
8 Correct 5 ms 376 KB n = 3
9 Correct 5 ms 376 KB n = 3
10 Correct 5 ms 376 KB n = 8
11 Correct 5 ms 376 KB n = 8
12 Correct 5 ms 380 KB n = 8
13 Correct 5 ms 376 KB n = 8
14 Correct 5 ms 376 KB n = 8
15 Correct 5 ms 376 KB n = 8
16 Correct 5 ms 376 KB n = 8
17 Correct 5 ms 376 KB n = 8
18 Correct 5 ms 408 KB n = 8
19 Correct 5 ms 376 KB n = 3
20 Correct 5 ms 376 KB n = 7
21 Correct 5 ms 376 KB n = 8
22 Correct 5 ms 376 KB n = 8
23 Correct 5 ms 376 KB n = 8
24 Correct 5 ms 376 KB n = 8
25 Correct 5 ms 376 KB n = 8
26 Correct 5 ms 376 KB n = 8
27 Correct 5 ms 376 KB n = 8
28 Correct 5 ms 376 KB n = 8
29 Correct 5 ms 376 KB n = 16
30 Correct 5 ms 376 KB n = 16
31 Correct 5 ms 368 KB n = 16
32 Correct 5 ms 376 KB n = 16
33 Correct 5 ms 376 KB n = 16
34 Correct 6 ms 376 KB n = 16
35 Correct 5 ms 376 KB n = 16
36 Correct 5 ms 380 KB n = 15
37 Correct 5 ms 376 KB n = 8
38 Correct 5 ms 376 KB n = 16
39 Correct 5 ms 376 KB n = 16
40 Correct 5 ms 376 KB n = 9
41 Correct 5 ms 376 KB n = 16
42 Correct 5 ms 376 KB n = 16
43 Correct 5 ms 376 KB n = 16
44 Correct 5 ms 376 KB n = 9
45 Correct 5 ms 376 KB n = 15
46 Correct 5 ms 380 KB n = 16
47 Correct 5 ms 376 KB n = 16
48 Correct 5 ms 376 KB n = 16
49 Correct 216 ms 12884 KB n = 199999
50 Correct 212 ms 14804 KB n = 199991
51 Correct 208 ms 14676 KB n = 199993
52 Correct 149 ms 11084 KB n = 152076
53 Correct 91 ms 7060 KB n = 93249
54 Correct 187 ms 12756 KB n = 199910
55 Correct 193 ms 13780 KB n = 199999
56 Correct 184 ms 12756 KB n = 199997
57 Correct 174 ms 12596 KB n = 171294
58 Correct 137 ms 9764 KB n = 140872
59 Correct 188 ms 12884 KB n = 199886
60 Correct 200 ms 13908 KB n = 199996
61 Correct 193 ms 13140 KB n = 200000
62 Correct 220 ms 17400 KB n = 199998
63 Correct 211 ms 17236 KB n = 200000
64 Correct 227 ms 17752 KB n = 199998
65 Correct 212 ms 14676 KB n = 200000
66 Correct 206 ms 13964 KB n = 190000
67 Correct 187 ms 13188 KB n = 177777
68 Correct 99 ms 7524 KB n = 100000
69 Correct 211 ms 14720 KB n = 200000
70 Correct 257 ms 18312 KB n = 200000
71 Correct 264 ms 18320 KB n = 200000
72 Correct 228 ms 14608 KB n = 200000
73 Correct 215 ms 14680 KB n = 200000
74 Correct 215 ms 14688 KB n = 200000
75 Correct 212 ms 14676 KB n = 200000
76 Correct 234 ms 14848 KB n = 200000
77 Correct 184 ms 12244 KB n = 200000
78 Correct 209 ms 15956 KB n = 200000
79 Correct 193 ms 13396 KB n = 184307
80 Correct 75 ms 5532 KB n = 76040
81 Correct 184 ms 13012 KB n = 199981
82 Correct 193 ms 13948 KB n = 199994
83 Correct 184 ms 13012 KB n = 199996
84 Correct 202 ms 17364 KB n = 199998
85 Correct 203 ms 17236 KB n = 200000
86 Correct 213 ms 17748 KB n = 199998
87 Correct 202 ms 14676 KB n = 200000
88 Correct 206 ms 14676 KB n = 200000
89 Correct 208 ms 14676 KB n = 200000
90 Correct 200 ms 14676 KB n = 200000
91 Correct 241 ms 18388 KB n = 200000
92 Correct 246 ms 18272 KB n = 200000