제출 #119753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
119753		someone_aa	Roller Coaster Railroad (IOI16_railroad)	C++17	30 / 100	1271 ms	88824 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;
        else if(curr < 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: 30 / 30
• Subtask 4: 0 / 36