Submission #420630

#	Time	Username	Problem	Language	Result	Execution time	Memory
420630		Peti	Roller Coaster Railroad (IOI16_railroad)	C++14	30 / 100	311 ms	52768 KiB

railroad

#include <bits/stdc++.h>
#include "railroad.h"

using namespace std;

vector<vector<int>> g;
vector<bool> volt;

int bejar(int akt){
    volt[akt] = true;
    int ret = 1;
    for(int x : g[akt])
        if(!volt[x])
            ret += bejar(x);
    return ret;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();

    vector<int> compr;
    compr.reserve(2*n);
    for(int x : s)
        compr.push_back(x);
    for(int x : t)
        compr.push_back(x);

    sort(compr.begin(), compr.end());
    compr.erase(unique(compr.begin(), compr.end()), compr.end());

    vector<int> va(n), vb(n);
    for(int i = 0; i < n; i++){
        va[i] = lower_bound(compr.begin(), compr.end(), s[i])-compr.begin();
        vb[i] = lower_bound(compr.begin(), compr.end(), t[i])-compr.begin();
    }

    int m = (int)compr.size();
    vector<int> fok(m, 0);
    g.resize(m);
    for(int i = 0; i < n; i++){
        fok[va[i]]++;
        fok[vb[i]]--;
        g[va[i]].push_back(vb[i]);
    }

    fok[0]--;
    fok[m-1]++;

    for(int i = 0; i < m-1; i++){
        if(fok[i] < 0)
            g[i].push_back(i+1);
        if(fok[i] <= 0)
            fok[i+1] += fok[i];
        else
            return 1;
    }

    volt.assign(m, false);
    if(fok[m-1] == 0 && bejar(0) == m)
        return 0;
    return 1;
}

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