제출 #431755

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
431755		phathnv	Roller Coaster Railroad (IOI16_railroad)	C++11	100 / 100	253 ms	21924 KiB

railroad

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