Submission #119750

#	Time	Username	Problem	Language	Result	Execution time	Memory
119750		someone_aa	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	1259 ms	88460 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
const int maxn = 400200;
set<ll>st;
map<ll,int>ind;
ll balance[maxn], n;
ll value[maxn];
ll cnt[maxn];
bool visited[maxn];
vector<int>g[maxn];

void dfs(int node) {
    if(visited[node]) return;
    visited[node] = true;
    for(int i:g[node]) {
        if(!visited[i])
            dfs(i);
    }
}


long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    n = (int) s.size();
    for(int i=0;i<n;i++) {
        st.insert(s[i]);
        st.insert(t[i]);
    }

    int br = 1;
    for(ll i:st) {
        value[br] = i;
        ind[i] = br;
        br++;
    }

    for(int i=0;i<n;i++) {
        s[i] = ind[s[i]];
        t[i] = ind[t[i]];

        g[s[i]].pb(t[i]);

        if(s[i] < t[i]) {
            cnt[s[i]]++;
            cnt[t[i]]--;
        }
        else {
            cnt[t[i]]--;
            cnt[s[i]]++;
        }
    }

    int curr = 0;
    for(int i=1;i<br;i++) {
        curr += cnt[i];
        //cout<<i<<": "<<curr<<"\n";
        if(curr > 1) return 1;
        g[i].pb(i+1);
    }

    dfs(1);

    for(int i=1;i<br;i++) {
        if(!visited[i]) return 1;
    }


    return 0;
}

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