oj.uz

답안 #794282

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
794282 2023-07-26T12:01:24 Z becaido Roller Coaster Railroad (IOI16_railroad) C++17
100 / 100
 204 ms 14824 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int INF = 1e9;
const int SIZE = 4e5 + 5;

int n, m;
ll ans;
int d[SIZE];
vector<int> lis;
int to[SIZE], h[SIZE];

int dsu(int x) {
    return x == to[x] ? x : (to[x] = dsu(to[x]));
}
bool mer(int a, int b) {
    a = dsu(a), b = dsu(b);
    if (a == b) return 0;
    if (h[a] < h[b]) swap(a, b);
    to[b] = a;
    h[a] += (h[a] == h[b]);
    return 1;
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    n = s.size();
    lis.clear();
    lis.pb(1), lis.pb(INF);
    lis.insert(lis.end(), s.begin(), s.end());
    lis.insert(lis.end(), t.begin(), t.end());
    sort(lis.begin(), lis.end());
    lis.erase(unique(lis.begin(), lis.end()), lis.end());
    m = lis.size();
    iota(to, to + m, 0);
    fill(h, h + m, 0);
    fill(d, d + m, 0);
    ans = 0;
    mer(0, m - 1);
    d[m - 1]++, d[0]--;
    FOR (i, 0, n - 1) {
        int l = lower_bound(lis.begin(), lis.end(), s[i]) - lis.begin();
        int r = lower_bound(lis.begin(), lis.end(), t[i]) - lis.begin();
        d[l]++, d[r]--;
        mer(l, r);
    }
    vector<pair<int, int>> e;
    FOR (i, 0, m - 2) {
        if (d[i] != 0) {
            mer(i, i + 1);
            if (d[i] > 0) ans += 1ll * d[i] * (lis[i + 1] - lis[i]);
        }
        e.pb(lis[i + 1] - lis[i], i);
        d[i + 1] += d[i];
    }
    sort(e.begin(), e.end());
    for (auto [w, i] : e) if (mer(i, i + 1)) ans += w;
    return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 14740 KB n = 199999
2 Correct 179 ms 14812 KB n = 199991
3 Correct 156 ms 14776 KB n = 199993
4 Correct 117 ms 12560 KB n = 152076
5 Correct 72 ms 7264 KB n = 93249
6 Correct 147 ms 13976 KB n = 199910
7 Correct 148 ms 14724 KB n = 199999
8 Correct 144 ms 13896 KB n = 199997
9 Correct 149 ms 13384 KB n = 171294
10 Correct 110 ms 11160 KB n = 140872
11 Correct 175 ms 14044 KB n = 199886
12 Correct 166 ms 14760 KB n = 199996
13 Correct 143 ms 14116 KB n = 200000
14 Correct 175 ms 14672 KB n = 199998
15 Correct 181 ms 14652 KB n = 200000
16 Correct 162 ms 14740 KB n = 199998
17 Correct 171 ms 14744 KB n = 200000
18 Correct 167 ms 14372 KB n = 190000
19 Correct 162 ms 13804 KB n = 177777
20 Correct 94 ms 7568 KB n = 100000
21 Correct 164 ms 14808 KB n = 200000
22 Correct 163 ms 14812 KB n = 200000
23 Correct 204 ms 14796 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB n = 2
2 Correct 0 ms 212 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 0 ms 212 KB n = 2
5 Correct 0 ms 212 KB n = 2
6 Correct 0 ms 212 KB n = 2
7 Correct 0 ms 212 KB n = 3
8 Correct 0 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 0 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 0 ms 212 KB n = 8
16 Correct 1 ms 212 KB n = 8
17 Correct 0 ms 212 KB n = 8
18 Correct 0 ms 212 KB n = 8
19 Correct 0 ms 212 KB n = 3
20 Correct 0 ms 212 KB n = 7
21 Correct 0 ms 212 KB n = 8
22 Correct 0 ms 212 KB n = 8
23 Correct 0 ms 212 KB n = 8
24 Correct 0 ms 212 KB n = 8
25 Correct 0 ms 212 KB n = 8
26 Correct 0 ms 212 KB n = 8
27 Correct 0 ms 212 KB n = 8
28 Correct 1 ms 212 KB n = 8
29 Correct 1 ms 212 KB n = 16
30 Correct 0 ms 212 KB n = 16
31 Correct 0 ms 212 KB n = 16
32 Correct 0 ms 216 KB n = 16
33 Correct 1 ms 212 KB n = 16
34 Correct 0 ms 212 KB n = 16
35 Correct 1 ms 212 KB n = 16
36 Correct 0 ms 212 KB n = 15
37 Correct 0 ms 212 KB n = 8
38 Correct 0 ms 212 KB n = 16
39 Correct 0 ms 212 KB n = 16
40 Correct 1 ms 212 KB n = 9
41 Correct 0 ms 212 KB n = 16
42 Correct 1 ms 212 KB n = 16
43 Correct 1 ms 212 KB n = 16
44 Correct 0 ms 212 KB n = 9
45 Correct 0 ms 212 KB n = 15
46 Correct 0 ms 212 KB n = 16
47 Correct 1 ms 212 KB n = 16
48 Correct 0 ms 212 KB n = 16
49 Correct 158 ms 14740 KB n = 199999
50 Correct 179 ms 14812 KB n = 199991
51 Correct 156 ms 14776 KB n = 199993
52 Correct 117 ms 12560 KB n = 152076
53 Correct 72 ms 7264 KB n = 93249
54 Correct 147 ms 13976 KB n = 199910
55 Correct 148 ms 14724 KB n = 199999
56 Correct 144 ms 13896 KB n = 199997
57 Correct 149 ms 13384 KB n = 171294
58 Correct 110 ms 11160 KB n = 140872
59 Correct 175 ms 14044 KB n = 199886
60 Correct 166 ms 14760 KB n = 199996
61 Correct 143 ms 14116 KB n = 200000
62 Correct 175 ms 14672 KB n = 199998
63 Correct 181 ms 14652 KB n = 200000
64 Correct 162 ms 14740 KB n = 199998
65 Correct 171 ms 14744 KB n = 200000
66 Correct 167 ms 14372 KB n = 190000
67 Correct 162 ms 13804 KB n = 177777
68 Correct 94 ms 7568 KB n = 100000
69 Correct 164 ms 14808 KB n = 200000
70 Correct 163 ms 14812 KB n = 200000
71 Correct 204 ms 14796 KB n = 200000
72 Correct 166 ms 14820 KB n = 200000
73 Correct 164 ms 14812 KB n = 200000
74 Correct 168 ms 14824 KB n = 200000
75 Correct 159 ms 14776 KB n = 200000
76 Correct 166 ms 14816 KB n = 200000
77 Correct 129 ms 10448 KB n = 200000
78 Correct 132 ms 10388 KB n = 200000
79 Correct 168 ms 14068 KB n = 184307
80 Correct 57 ms 6068 KB n = 76040
81 Correct 145 ms 14044 KB n = 199981
82 Correct 153 ms 14720 KB n = 199994
83 Correct 142 ms 14152 KB n = 199996
84 Correct 155 ms 14728 KB n = 199998
85 Correct 162 ms 14652 KB n = 200000
86 Correct 154 ms 14796 KB n = 199998
87 Correct 164 ms 14812 KB n = 200000
88 Correct 162 ms 14816 KB n = 200000
89 Correct 162 ms 14736 KB n = 200000
90 Correct 156 ms 14732 KB n = 200000
91 Correct 172 ms 14780 KB n = 200000
92 Correct 153 ms 14796 KB n = 200000