oj.uz

답안 #151168

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
151168 2019-09-02T01:37:43 Z tri Roller Coaster Railroad (IOI16_railroad) C++14
100 / 100
 1129 ms 58732 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = false;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;

struct DSU {
    vi anc;

    void init(int N) {
        anc.resize(N);
        for (int i = 0; i < N; i++) {
            anc[i] = i;
        }
    }

    int fRt(int i) {
        return anc[i] == i ? i : anc[i] = fRt(anc[i]);
    }

    bool merge(int a, int b) {
        a = fRt(a), b = fRt(b);
        if (a == b) {
            return false;
        }
        anc[a] = b;
        return true;
    }
} dsu;

ll plan_roller_coaster(vi s, vi e) {
    s.pb(1e9);
    e.pb(1);

    int N = s.size();
    set<int> pts;

    for (int i = 0; i < N; i++) {
        pts.insert(s[i]);
        pts.insert(e[i]);
    }

    int PS = pts.size();

    map<int, int> pMap;
    vi ptl;

    int cP = 0;
    for (int x : pts) {
        pMap[x] = cP++;
        ptl.pb(x);
    }

    for (int i = 0; i < N; i++) {
        s[i] = pMap[s[i]];
        e[i] = pMap[e[i]];
    }
    ps("mapped");

    vi up(PS, 0);
    vi down(PS, 0);

    for (int i = 0; i < N; i++) {
        if (s[i] < e[i]) {
            up[s[i]]++;
            up[e[i]]--;
        } else {
            down[e[i]]++;
            down[s[i]]--;
        }
    }
    int uSum = 0, dSum = 0;

    for (int i = 0; i < PS; i++) {
        uSum += up[i];
        dSum += down[i];
        up[i] = uSum;
        down[i] = dSum;
    }

    ps("segmented");
    ps(ptl);
    ps(s);
    ps(e);

    dsu.init(PS);

    ll cost = 0;

    for (int i = 0; i < N; i++) {
        ps("merge:", s[i], e[i]);
        dsu.merge(s[i], e[i]);
    }

    for (int i = 0; i < PS - 1; i++) {
        if (up[i] > down[i]) {
            cost += (ll) (up[i] - down[i]) * (ptl[i + 1] - ptl[i]);
            ps("merge:", i, i + 1);
            dsu.merge(i, i + 1); // will fall through
        }
        if (up[i] < down[i]) {
            ps("merge:", i, i + 1);
            dsu.merge(i, i + 1); // will jump up
        }
    }

    for (int i = 0; i < PS; i++) {
        pr(dsu.fRt(i), " ");
    }
    ps();

    vector<pi> mstE;
    for (int i = 0; i < PS - 1; i++) {
        mstE.pb({ptl[i + 1] - ptl[i], i});
    }

    sort(mstE.begin(), mstE.end());
    for (pi x : mstE) {
        int c1 = dsu.fRt(x.s);
        int c2 = dsu.fRt(x.s + 1);
        if (c1 != c2) {
            dsu.merge(c1, c2);
            cost += x.f;
        }
    }

    return cost;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1012 ms 55480 KB n = 199999
2 Correct 1065 ms 55576 KB n = 199991
3 Correct 1028 ms 55388 KB n = 199993
4 Correct 776 ms 42976 KB n = 152076
5 Correct 410 ms 26312 KB n = 93249
6 Correct 844 ms 46440 KB n = 199910
7 Correct 867 ms 54380 KB n = 199999
8 Correct 736 ms 47244 KB n = 199997
9 Correct 866 ms 48076 KB n = 171294
10 Correct 687 ms 40416 KB n = 140872
11 Correct 823 ms 47056 KB n = 199886
12 Correct 861 ms 54812 KB n = 199996
13 Correct 780 ms 49020 KB n = 200000
14 Correct 821 ms 55632 KB n = 199998
15 Correct 833 ms 54224 KB n = 200000
16 Correct 831 ms 55852 KB n = 199998
17 Correct 979 ms 58576 KB n = 200000
18 Correct 1064 ms 53208 KB n = 190000
19 Correct 901 ms 52612 KB n = 177777
20 Correct 436 ms 28004 KB n = 100000
21 Correct 941 ms 55380 KB n = 200000
22 Correct 943 ms 55504 KB n = 200000
23 Correct 1108 ms 55444 KB n = 200000

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB n = 2
2 Correct 2 ms 376 KB n = 2
3 Correct 2 ms 256 KB n = 2
4 Correct 2 ms 256 KB n = 2
5 Correct 2 ms 376 KB n = 2
6 Correct 2 ms 252 KB n = 2
7 Correct 2 ms 256 KB n = 3
8 Correct 2 ms 252 KB n = 3
9 Correct 2 ms 256 KB n = 3
10 Correct 2 ms 256 KB n = 8
11 Correct 2 ms 256 KB n = 8
12 Correct 2 ms 376 KB n = 8
13 Correct 2 ms 256 KB n = 8
14 Correct 2 ms 256 KB n = 8
15 Correct 2 ms 252 KB n = 8
16 Correct 2 ms 256 KB n = 8
17 Correct 2 ms 376 KB n = 8
18 Correct 2 ms 256 KB n = 8
19 Correct 2 ms 256 KB n = 3
20 Correct 2 ms 376 KB n = 7
21 Correct 2 ms 256 KB n = 8
22 Correct 2 ms 256 KB n = 8
23 Correct 2 ms 356 KB n = 8
24 Correct 3 ms 376 KB n = 8
25 Correct 2 ms 256 KB n = 8
26 Correct 2 ms 376 KB n = 8
27 Correct 2 ms 376 KB n = 8
28 Correct 2 ms 376 KB n = 8
29 Correct 2 ms 376 KB n = 16
30 Correct 2 ms 256 KB n = 16
31 Correct 2 ms 256 KB n = 16
32 Correct 2 ms 252 KB n = 16
33 Correct 2 ms 376 KB n = 16
34 Correct 2 ms 376 KB n = 16
35 Correct 2 ms 376 KB n = 16
36 Correct 2 ms 376 KB n = 15
37 Correct 2 ms 256 KB n = 8
38 Correct 2 ms 256 KB n = 16
39 Correct 2 ms 376 KB n = 16
40 Correct 2 ms 376 KB n = 9
41 Correct 2 ms 256 KB n = 16
42 Correct 2 ms 256 KB n = 16
43 Correct 2 ms 256 KB n = 16
44 Correct 2 ms 256 KB n = 9
45 Correct 2 ms 256 KB n = 15
46 Correct 2 ms 376 KB n = 16
47 Correct 2 ms 376 KB n = 16
48 Correct 2 ms 376 KB n = 16
49 Correct 1012 ms 55480 KB n = 199999
50 Correct 1065 ms 55576 KB n = 199991
51 Correct 1028 ms 55388 KB n = 199993
52 Correct 776 ms 42976 KB n = 152076
53 Correct 410 ms 26312 KB n = 93249
54 Correct 844 ms 46440 KB n = 199910
55 Correct 867 ms 54380 KB n = 199999
56 Correct 736 ms 47244 KB n = 199997
57 Correct 866 ms 48076 KB n = 171294
58 Correct 687 ms 40416 KB n = 140872
59 Correct 823 ms 47056 KB n = 199886
60 Correct 861 ms 54812 KB n = 199996
61 Correct 780 ms 49020 KB n = 200000
62 Correct 821 ms 55632 KB n = 199998
63 Correct 833 ms 54224 KB n = 200000
64 Correct 831 ms 55852 KB n = 199998
65 Correct 979 ms 58576 KB n = 200000
66 Correct 1064 ms 53208 KB n = 190000
67 Correct 901 ms 52612 KB n = 177777
68 Correct 436 ms 28004 KB n = 100000
69 Correct 941 ms 55380 KB n = 200000
70 Correct 943 ms 55504 KB n = 200000
71 Correct 1108 ms 55444 KB n = 200000
72 Correct 1129 ms 55456 KB n = 200000
73 Correct 1048 ms 55576 KB n = 200000
74 Correct 1060 ms 55488 KB n = 200000
75 Correct 986 ms 55404 KB n = 200000
76 Correct 991 ms 55448 KB n = 200000
77 Correct 517 ms 35536 KB n = 200000
78 Correct 552 ms 32344 KB n = 200000
79 Correct 965 ms 51280 KB n = 184307
80 Correct 306 ms 21916 KB n = 76040
81 Correct 830 ms 47056 KB n = 199981
82 Correct 870 ms 54768 KB n = 199994
83 Correct 819 ms 48976 KB n = 199996
84 Correct 806 ms 55632 KB n = 199998
85 Correct 822 ms 54224 KB n = 200000
86 Correct 845 ms 55888 KB n = 199998
87 Correct 973 ms 58732 KB n = 200000
88 Correct 992 ms 56040 KB n = 200000
89 Correct 969 ms 58668 KB n = 200000
90 Correct 961 ms 55480 KB n = 200000
91 Correct 933 ms 55556 KB n = 200000
92 Correct 983 ms 55452 KB n = 200000