제출 #559160

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
559160		elazarkoren	Roller Coaster Railroad (IOI16_railroad)	C++17	30 / 100	187 ms	18736 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int infinity = 2e9;
const int MAX_N = 2e5 + 5;

vi vals;
inline int Val(int x) {
    return lower_bound(all(vals), x) - vals.begin();
}

int add[2 * MAX_N];

struct Dsu {
    vi par, sz;
    Dsu() {}
    Dsu(int n) {
        par.resize(n), sz.resize(n, 1);
        iota(all(par), 0);
    }
    int Find(int i) {
        return par[i] == i ? i : par[i] = Find(par[i]);
    }
    void Union(int a, int b) {
        int pa = Find(a), pb = Find(b);
        if (pa == pb) return;
        if (sz[pa] < sz[pb]) swap(pa, pb);
        par[pb] = pa;
        sz[pa] += sz[pb];
    }
};

ll plan_roller_coaster(vi s, vi t) {
    int n = s.size();
    s.push_back(infinity), t.push_back(0);
    for (int i = 0; i <= n; i++) vals.push_back(s[i]), vals.push_back(t[i]);
    sort(all(vals));
    vals.erase(unique(all(vals)), vals.end());
    for (int &x : s) {
        x = Val(x);
        add[x]++;
    }
    for (int &x : t) {
        x = Val(x);
        add[x]--;
    }
    int sz = vals.size();
    vii edges;
    for (int i = 0; i <= n; i++) edges.push_back({s[i], t[i]});
    for (int i = 0, balance = 0; i < sz; i++) {
        balance += add[i];
        if (balance > 0) return 1;
        if (balance < 0) edges.push_back({i, i + 1});
    }
    Dsu dsu(sz);
    for (auto [a, b] : edges) dsu.Union(a, b);
    return dsu.sz[dsu.Find(1)] != sz;
}
//5
//5 4
//6 2
//3 5
//7 7
//8 3

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 30 / 30
• Subtask 4: 0 / 36