제출 #151168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
151168		tri	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	1129 ms	58732 KiB

railroad

#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 / 11
• Subtask 2: 23 / 23
• Subtask 3: 30 / 30
• Subtask 4: 36 / 36