Submission #469327

#	Time	Username	Problem	Language	Result	Execution time	Memory
469327		luciocf	Roller Coaster Railroad (IOI16_railroad)	C++14	30 / 100	912 ms	58460 KiB

railroad

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

using namespace std;

const int maxn = 4e5+10;

map<int, int> mp;

int soma[maxn];
bool mark[maxn];

vector<int> grafo[maxn];

void dfs(int u)
{
    mark[u] = 1;
    for (auto v: grafo[u])
        if (!mark[v])
            dfs(v);
}

long long plan_roller_coaster(vector<int> s, vector<int> t)
{
    s.push_back(1e9); s.push_back(1);
    int n = (int) s.size();

    for (int i = 0; i < n; i++)
        mp[s[i]] = mp[t[i]] = 0;
    
    int aux = 0;
    for (auto &x: mp)
        x.second = aux++;

    vector<int> v;
    for (int i = 0; i < n; i++)
    {
        soma[mp[s[i]]]++;
        soma[mp[t[i]]]--;

        v.push_back(mp[s[i]]);
        v.push_back(mp[t[i]]);

        grafo[mp[s[i]]].push_back(mp[t[i]]);
    }

    for (int i = 0; i < aux; i++)
    {
        if (i) soma[i] += soma[i-1];

        if (soma[i] > 0) return 1;
        else if (soma[i] < 0) grafo[i].push_back(i+1);
    }

    dfs(0);

    for (int i = 0; i < aux; i++)
        if (!mark[i])
            return 1;

    return 0;
}

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