oj.uz

답안 #431755

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431755 2021-06-17T15:05:55 Z phathnv Roller Coaster Railroad (IOI16_railroad) C++11
100 / 100
 253 ms 21924 KB 
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, w;
    Edge(int _u, int _v, int _w) {
        u = _u;
        v = _v;
        w = _w;
    }
    bool operator < (const Edge &oth) {
        return w < oth.w;
    }
};

struct DSU {
    int n;
    vector<int> root, rnk;
    DSU(int _n) {
        n = _n;
        root.assign(n, 0);
        rnk.assign(n, 0);
        iota(root.begin(), root.end(), 0);
    }
    int findRoot(int u) {
        if (u == root[u])
            return u;
        return root[u] = findRoot(root[u]);
    }
    bool unite(int u, int v) {
        u = findRoot(u);
        v = findRoot(v);
        if (u == v)
            return 0;
        if (rnk[u] < rnk[v])
            swap(u, v);
        root[v] = u;
        rnk[u] += (rnk[u] == rnk[v]);
        return 1;
    }
};

long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int m = (int) s.size();
    vector<int> xCoor;
    for (int i = 0; i < m; i++) {
        xCoor.push_back(s[i]);
        xCoor.push_back(t[i]);
    }
    xCoor.push_back(1);
    xCoor.push_back(1e9);
    sort(xCoor.begin(), xCoor.end());
    xCoor.resize(unique(xCoor.begin(), xCoor.end()) - xCoor.begin());
    int nX = xCoor.size();
    DSU dsu(nX);
    vector<int> deg(nX, 0);
    for (int i = 0; i < m; i++) {
        s[i] = lower_bound(xCoor.begin(), xCoor.end(), s[i]) - xCoor.begin();
        t[i] = lower_bound(xCoor.begin(), xCoor.end(), t[i]) - xCoor.begin();
        deg[s[i]]--;
        deg[t[i]]++;
        dsu.unite(s[i], t[i]);
    }
    deg[0]++;
    deg[nX - 1]--;
    dsu.unite(0, nX - 1);
    vector<int> outPos, inPos;
    for (int i = 0; i < nX; i++) {
        while (deg[i] > 0) {
            outPos.push_back(i);
            deg[i]--;
        }
        while (deg[i] < 0) {
            inPos.push_back(i);
            deg[i]++;
        }
    }
    long long ans = 0;
    vector<int> cnt(nX, 0);
    for (int i = 0; i < (int) outPos.size(); i++) {
        int u = outPos[i], v = inPos[i];
        ans += max(0, xCoor[u] - xCoor[v]);
        cnt[min(u, v)]++;
        cnt[max(u, v)]--;
    }
    for (int i = 1; i < nX; i++)
        cnt[i] += cnt[i - 1];
    vector<Edge> edges;
    for (int i = 0; i < nX - 1; i++)
        if (cnt[i])
            dsu.unite(i, i + 1);
        else
            edges.push_back(Edge(i, i + 1, xCoor[i + 1] - xCoor[i]));
    sort(edges.begin(), edges.end());
    for (Edge e : edges)
        ans += dsu.unite(e.u, e.v) * e.w;
    return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 238 ms 17656 KB n = 199999
2 Correct 245 ms 18072 KB n = 199991
3 Correct 227 ms 17656 KB n = 199993
4 Correct 174 ms 12760 KB n = 152076
5 Correct 92 ms 7892 KB n = 93249
6 Correct 198 ms 14252 KB n = 199910
7 Correct 223 ms 17056 KB n = 199999
8 Correct 208 ms 14220 KB n = 199997
9 Correct 179 ms 14140 KB n = 171294
10 Correct 170 ms 12244 KB n = 140872
11 Correct 199 ms 14412 KB n = 199886
12 Correct 203 ms 17296 KB n = 199996
13 Correct 187 ms 15140 KB n = 200000
14 Correct 202 ms 20336 KB n = 199998
15 Correct 199 ms 20768 KB n = 200000
16 Correct 249 ms 21388 KB n = 199998
17 Correct 187 ms 17716 KB n = 200000
18 Correct 191 ms 17264 KB n = 190000
19 Correct 177 ms 15896 KB n = 177777
20 Correct 87 ms 8856 KB n = 100000
21 Correct 196 ms 17956 KB n = 200000
22 Correct 246 ms 21876 KB n = 200000
23 Correct 232 ms 21876 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB n = 2
2 Correct 1 ms 204 KB n = 2
3 Correct 1 ms 204 KB n = 2
4 Correct 0 ms 204 KB n = 2
5 Correct 1 ms 204 KB n = 2
6 Correct 1 ms 204 KB n = 2
7 Correct 1 ms 204 KB n = 3
8 Correct 1 ms 204 KB n = 3
9 Correct 1 ms 204 KB n = 3
10 Correct 1 ms 204 KB n = 8
11 Correct 1 ms 204 KB n = 8
12 Correct 1 ms 204 KB n = 8
13 Correct 1 ms 204 KB n = 8
14 Correct 1 ms 204 KB n = 8
15 Correct 1 ms 204 KB n = 8
16 Correct 1 ms 204 KB n = 8
17 Correct 1 ms 204 KB n = 8
18 Correct 1 ms 288 KB n = 8
19 Correct 1 ms 204 KB n = 3
20 Correct 1 ms 204 KB n = 7
21 Correct 1 ms 204 KB n = 8
22 Correct 1 ms 204 KB n = 8
23 Correct 1 ms 204 KB n = 8
24 Correct 1 ms 204 KB n = 8
25 Correct 1 ms 204 KB n = 8
26 Correct 1 ms 204 KB n = 8
27 Correct 1 ms 204 KB n = 8
28 Correct 1 ms 292 KB n = 8
29 Correct 1 ms 204 KB n = 16
30 Correct 1 ms 204 KB n = 16
31 Correct 1 ms 204 KB n = 16
32 Correct 1 ms 204 KB n = 16
33 Correct 1 ms 292 KB n = 16
34 Correct 1 ms 204 KB n = 16
35 Correct 1 ms 204 KB n = 16
36 Correct 1 ms 204 KB n = 15
37 Correct 1 ms 204 KB n = 8
38 Correct 1 ms 204 KB n = 16
39 Correct 1 ms 204 KB n = 16
40 Correct 1 ms 204 KB n = 9
41 Correct 1 ms 204 KB n = 16
42 Correct 1 ms 204 KB n = 16
43 Correct 1 ms 204 KB n = 16
44 Correct 1 ms 204 KB n = 9
45 Correct 1 ms 292 KB n = 15
46 Correct 1 ms 292 KB n = 16
47 Correct 1 ms 204 KB n = 16
48 Correct 1 ms 296 KB n = 16
49 Correct 238 ms 17656 KB n = 199999
50 Correct 245 ms 18072 KB n = 199991
51 Correct 227 ms 17656 KB n = 199993
52 Correct 174 ms 12760 KB n = 152076
53 Correct 92 ms 7892 KB n = 93249
54 Correct 198 ms 14252 KB n = 199910
55 Correct 223 ms 17056 KB n = 199999
56 Correct 208 ms 14220 KB n = 199997
57 Correct 179 ms 14140 KB n = 171294
58 Correct 170 ms 12244 KB n = 140872
59 Correct 199 ms 14412 KB n = 199886
60 Correct 203 ms 17296 KB n = 199996
61 Correct 187 ms 15140 KB n = 200000
62 Correct 202 ms 20336 KB n = 199998
63 Correct 199 ms 20768 KB n = 200000
64 Correct 249 ms 21388 KB n = 199998
65 Correct 187 ms 17716 KB n = 200000
66 Correct 191 ms 17264 KB n = 190000
67 Correct 177 ms 15896 KB n = 177777
68 Correct 87 ms 8856 KB n = 100000
69 Correct 196 ms 17956 KB n = 200000
70 Correct 246 ms 21876 KB n = 200000
71 Correct 232 ms 21876 KB n = 200000
72 Correct 207 ms 17704 KB n = 200000
73 Correct 226 ms 17964 KB n = 200000
74 Correct 199 ms 17664 KB n = 200000
75 Correct 196 ms 17668 KB n = 200000
76 Correct 207 ms 17668 KB n = 200000
77 Correct 148 ms 11984 KB n = 200000
78 Correct 170 ms 16564 KB n = 200000
79 Correct 194 ms 16596 KB n = 184307
80 Correct 67 ms 6632 KB n = 76040
81 Correct 208 ms 14388 KB n = 199981
82 Correct 184 ms 17204 KB n = 199994
83 Correct 182 ms 15136 KB n = 199996
84 Correct 209 ms 20472 KB n = 199998
85 Correct 194 ms 20512 KB n = 200000
86 Correct 211 ms 21384 KB n = 199998
87 Correct 197 ms 17720 KB n = 200000
88 Correct 210 ms 16936 KB n = 200000
89 Correct 204 ms 17720 KB n = 200000
90 Correct 215 ms 18072 KB n = 200000
91 Correct 221 ms 21816 KB n = 200000
92 Correct 253 ms 21924 KB n = 200000