Submission #799457

#	Time	Username	Problem	Language	Result	Execution time	Memory
799457		PixelCat	Roller Coaster Railroad (IOI16_railroad)	C++14	30 / 100	94 ms	17008 KiB

railroad

#include "railroad.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 200'000;

struct DSU {
    int p[MAXN + 10];
    void init() {
        memset(p, -1, sizeof(p));
    }
    int find(int n) {
        if(p[n] < 0) return n;
        return p[n] = find(p[n]);
    }
    void uni(int a, int b) {
        // cerr << a << " " << b << "\n";
        a = find(a); b = find(b);
        assert(a != b);
        p[b] = a;
    }
    bool same(int a, int b) {
        return find(a) == find(b);
    }
} dsu;

long long plan_roller_coaster(std::vector<int32_t> s, std::vector<int32_t> t) {
    int n = sz(s);
    vector<pii> vs, vt;
    For(i, 0, n - 1) {
        vs.eb(s[i], i + 1);
        vt.eb(t[i], i + 1);
    }
    sort(all(vs));
    sort(all(vt));
    int ptr = 0;
    vector<int> stk;
    stk.eb(0);
    dsu.init();
    for(auto &p:vs) {
        // cerr << "owo? " << p.F << " " << p.S << "\n";
        while(ptr < n && vt[ptr].F <= p.F) {
            stk.eb(vt[ptr].S);
            ptr++;
        }
        if(sz(stk) && !dsu.same(stk.back(), p.S)) {
            dsu.uni(stk.back(), p.S);
            stk.pop_back();
        } else if(sz(stk) >= 2 && !dsu.same(stk[sz(stk) - 2], p.S)) {
            dsu.uni(stk[sz(stk) - 2], p.S);
            swap(stk[sz(stk) - 1], stk[sz(stk) - 2]);
            stk.pop_back();
        } else {
            return 1;
        }
    }
    return 0;
}

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