Submission #71267

#	Time	Username	Problem	Language	Result	Execution time	Memory
71267		evpipis	Roller Coaster Railroad (IOI16_railroad)	C++11	0 / 100	373 ms	14708 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

//#define TEST

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;

const int inf = 1e9+5, len = 2e5+5;
vector<pair<ii, int> > vec;
set<int> mys;
int pos[len], par[len];

bool comp(pair<ii, int> a, pair<ii, int> b){
    if (a.fi.fi > b.fi.fi) return true;
    if (a.fi.fi < b.fi.fi) return false;
    return (a.fi.se < b.fi.se);
}

int fin(int i){
    if (par[i] == i) return i;
    return par[i] = fin(par[i]);
}

void join(int i, int j){
    i = fin(i), j = fin(j);
    if (i != j)
        par[i] = j;
}

long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = (int) s.size(), ans = 0;
    for (int i = 0; i < n; i++){
        //printf("%d %d\n", s[i], t[i]);
        vec.pb(mp(mp(s[i], 0), i));
        vec.pb(mp(mp(t[i], 1), i));
    }

    for (int i = 0; i < 2*n; i++)
        par[i] = i;

    vec.pb(mp(mp(inf, 0), n));
    vec.pb(mp(mp(0, 1), n));
    sort(vec.begin(), vec.end(), comp);

    for (int i = 0; i < vec.size(); i++)
        if (vec[i].fi.se)
            pos[vec[i].se] = i;

    for (int i = 0; i < vec.size()-1; i++){
        //printf("(%d, %d)\n", vec[i].fi.se, pos[vec[i].se]);
        if (vec[i].fi.se == 0){
            mys.insert(pos[vec[i].se]);
        }
        else{
            set<int>::iterator it = mys.upper_bound(i);
            if (it != mys.end()){
                join(i, *it);
                mys.erase(it);
                //mys.erase(i);
            }
            else if (mys.size() >= 1 && fin(i) != fin(*mys.begin())){
                join(i, *mys.begin());
                mys.erase(mys.begin());
                //mys.erase(i);
            }
            else if (mys.size() >= 2){
                join(i, *prev(mys.end()));
                mys.erase(prev(mys.end()));
            }
            else
                ans = 1;
        }
        /*for (auto it: mys)
            printf("%d ", it);
        printf("\n");
        printf("i = %d, ans = %d\n", i, ans);*/
    }

    return ans;
}

#ifdef TEST
int main() {
    //freopen("01", "r", stdin);
    int n;
    assert(1 == scanf("%d", &n));
    std::vector<int> s(n), t(n);
    for (int i = 0; i < n; ++i)
        assert(2 == scanf("%d%d", &s[i], &t[i]));
    long long ans = plan_roller_coaster(s, t);
    printf("%lld\n", ans);
    return 0;
}
#endif // TEST

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:51:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++)
                     ~~^~~~~~~~~~~~
railroad.cpp:55:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size()-1; i++){
                     ~~^~~~~~~~~~~~~~

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