oj.uz

답안 #135900

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
135900 2019-07-24T13:14:53 Z Kastanda Roller Coaster Railroad (IOI16_railroad) C++11
100 / 100
 231 ms 25200 KB 
// ItnoE
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int N = 200005;
int P[N];
int Find(int v)
{
    return (P[v] < 0 ? v : (P[v] = Find(P[v])));
}
inline bool Merge(int v, int u)
{
    v = Find(v);
    u = Find(u);
    if (v == u)
        return 0;
    P[v] = u;
    return 1;
}
int64_t plan_roller_coaster(vector < int > S, vector < int > T)
{
    int n = (int)S.size();
    vector < pair < int , pair < int , int > > > A, E;
    for (int i = 0; i < n; i ++)
    {
        A.push_back({S[i], {1, i}});
        A.push_back({T[i], {-1, i}});
    }
    A.push_back({(int)1e9, {1, n}});
    A.push_back({1, {-1, n ++}});
    sort(A.begin(), A.end());
    int SM = 0;
    ll tot = 0;
    memset(P, -1, sizeof(P));
    for (int i = 0; i + 1 < (int)A.size(); i ++)
    {
        SM += A[i].y.x;
        tot += max(SM, 0) * (ll)(A[i + 1].x - A[i].x);
        E.push_back({A[i + 1].x - A[i].x, {A[i].y.y, A[i + 1].y.y}});
        if (A[i].x == A[i + 1].x || SM)
            Merge(A[i].y.y, A[i + 1].y.y);
    }
    sort(E.begin(), E.end());
    for (auto e : E)
        if (Merge(e.y.x, e.y.y))
            tot += e.x;
    return (tot);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 228 ms 18980 KB n = 199999
2 Correct 229 ms 22120 KB n = 199991
3 Correct 229 ms 22036 KB n = 199993
4 Correct 172 ms 18892 KB n = 152076
5 Correct 109 ms 11328 KB n = 93249
6 Correct 207 ms 20860 KB n = 199910
7 Correct 198 ms 21340 KB n = 199999
8 Correct 198 ms 20956 KB n = 199997
9 Correct 193 ms 20316 KB n = 171294
10 Correct 160 ms 18524 KB n = 140872
11 Correct 203 ms 20964 KB n = 199886
12 Correct 207 ms 21340 KB n = 199996
13 Correct 205 ms 21160 KB n = 200000
14 Correct 220 ms 21404 KB n = 199998
15 Correct 212 ms 21204 KB n = 200000
16 Correct 222 ms 21516 KB n = 199998
17 Correct 206 ms 25180 KB n = 200000
18 Correct 211 ms 21812 KB n = 190000
19 Correct 182 ms 23580 KB n = 177777
20 Correct 104 ms 11596 KB n = 100000
21 Correct 216 ms 22080 KB n = 200000
22 Correct 219 ms 22108 KB n = 200000
23 Correct 217 ms 22108 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1148 KB n = 2
2 Correct 2 ms 1144 KB n = 2
3 Correct 3 ms 1144 KB n = 2
4 Correct 3 ms 1144 KB n = 2
5 Correct 3 ms 1144 KB n = 2
6 Correct 3 ms 1144 KB n = 2
7 Correct 3 ms 1144 KB n = 3
8 Correct 3 ms 1144 KB n = 3
9 Correct 3 ms 1144 KB n = 3
10 Correct 2 ms 1144 KB n = 8
11 Correct 3 ms 1144 KB n = 8
12 Correct 3 ms 1144 KB n = 8
13 Correct 3 ms 1144 KB n = 8
14 Correct 3 ms 1144 KB n = 8
15 Correct 3 ms 1144 KB n = 8
16 Correct 3 ms 1144 KB n = 8
17 Correct 3 ms 1144 KB n = 8
18 Correct 3 ms 1144 KB n = 8
19 Correct 3 ms 1144 KB n = 3
20 Correct 3 ms 1144 KB n = 7
21 Correct 3 ms 1144 KB n = 8
22 Correct 3 ms 1144 KB n = 8
23 Correct 3 ms 1144 KB n = 8
24 Correct 3 ms 1144 KB n = 8
25 Correct 3 ms 1144 KB n = 8
26 Correct 3 ms 1144 KB n = 8
27 Correct 3 ms 1148 KB n = 8
28 Correct 3 ms 1144 KB n = 8
29 Correct 3 ms 1144 KB n = 16
30 Correct 3 ms 1144 KB n = 16
31 Correct 3 ms 1144 KB n = 16
32 Correct 3 ms 1272 KB n = 16
33 Correct 3 ms 1144 KB n = 16
34 Correct 3 ms 1144 KB n = 16
35 Correct 3 ms 1144 KB n = 16
36 Correct 3 ms 1144 KB n = 15
37 Correct 3 ms 1144 KB n = 8
38 Correct 3 ms 1144 KB n = 16
39 Correct 3 ms 1144 KB n = 16
40 Correct 2 ms 1020 KB n = 9
41 Correct 2 ms 1144 KB n = 16
42 Correct 2 ms 1144 KB n = 16
43 Correct 2 ms 1144 KB n = 16
44 Correct 3 ms 1144 KB n = 9
45 Correct 3 ms 1144 KB n = 15
46 Correct 3 ms 1020 KB n = 16
47 Correct 3 ms 1144 KB n = 16
48 Correct 3 ms 1148 KB n = 16
49 Correct 228 ms 18980 KB n = 199999
50 Correct 229 ms 22120 KB n = 199991
51 Correct 229 ms 22036 KB n = 199993
52 Correct 172 ms 18892 KB n = 152076
53 Correct 109 ms 11328 KB n = 93249
54 Correct 207 ms 20860 KB n = 199910
55 Correct 198 ms 21340 KB n = 199999
56 Correct 198 ms 20956 KB n = 199997
57 Correct 193 ms 20316 KB n = 171294
58 Correct 160 ms 18524 KB n = 140872
59 Correct 203 ms 20964 KB n = 199886
60 Correct 207 ms 21340 KB n = 199996
61 Correct 205 ms 21160 KB n = 200000
62 Correct 220 ms 21404 KB n = 199998
63 Correct 212 ms 21204 KB n = 200000
64 Correct 222 ms 21516 KB n = 199998
65 Correct 206 ms 25180 KB n = 200000
66 Correct 211 ms 21812 KB n = 190000
67 Correct 182 ms 23580 KB n = 177777
68 Correct 104 ms 11596 KB n = 100000
69 Correct 216 ms 22080 KB n = 200000
70 Correct 219 ms 22108 KB n = 200000
71 Correct 217 ms 22108 KB n = 200000
72 Correct 231 ms 22112 KB n = 200000
73 Correct 230 ms 22036 KB n = 200000
74 Correct 230 ms 22188 KB n = 200000
75 Correct 203 ms 21980 KB n = 200000
76 Correct 217 ms 21992 KB n = 200000
77 Correct 206 ms 22108 KB n = 200000
78 Correct 194 ms 21980 KB n = 200000
79 Correct 206 ms 20976 KB n = 184307
80 Correct 83 ms 10212 KB n = 76040
81 Correct 199 ms 20960 KB n = 199981
82 Correct 207 ms 21596 KB n = 199994
83 Correct 208 ms 21048 KB n = 199996
84 Correct 214 ms 21280 KB n = 199998
85 Correct 212 ms 21240 KB n = 200000
86 Correct 221 ms 21568 KB n = 199998
87 Correct 206 ms 25180 KB n = 200000
88 Correct 215 ms 22748 KB n = 200000
89 Correct 202 ms 25200 KB n = 200000
90 Correct 217 ms 22108 KB n = 200000
91 Correct 218 ms 22108 KB n = 200000
92 Correct 206 ms 22212 KB n = 200000