Submission #266481

#	Time	Username	Problem	Language	Result	Execution time	Memory
266481		sealnot123	Roller Coaster Railroad (IOI16_railroad)	C++14	30 / 100	339 ms	34152 KiB

railroad

#include "railroad.h"
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define ROF(i, a, b) for(int i=(a); i>=(b); --i)
#define make_unique(a) sort(all((a))), (a).resize(unique(all((a)))-(a).begin())

using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
typedef double DD;
typedef long double LD;
typedef pair<LL,LL> PLL;
typedef pair<DD,DD> PDD;
typedef vector<int> VI;
typedef vector<LL> VL;

const int N = 400004;
int n;
vector<int> mark, comp, dp, g[N];
queue<int> bfs;
LL plan_roller_coaster(VI s, VI t) {
    int n = SZ(s);
    FOR(i,0,n-1) comp.pb(s[i]), comp.pb(t[i]);
    comp.pb(0); comp.pb(1e9+2);
    make_unique(comp);
    int m = SZ(comp);
    dp.resize(m, 0);
    mark.resize(m, 0);
    FOR(i,0,n-1){
        s[i] = lower_bound(all(comp), s[i])-comp.begin();
        t[i] = lower_bound(all(comp), t[i])-comp.begin();
        if(s[i] == t[i]) continue;
        dp[s[i]]++;
        dp[t[i]]--;
        g[s[i]].pb(t[i]);
    }
    --dp[1];
    g[0].pb(1);
    FOR(i, 1, m-2){
        if(dp[i] > 0) return 1;
        if(dp[i] == 0) continue;
        dp[i+1] += dp[i];
        dp[i] = 0;
        g[i].pb(i+1);
    }
    // check if the same component
    bfs.push(0);
    mark[0] = 1;
    int cnt = 0;
    while(!bfs.empty()){
        int u = bfs.front();
        ++cnt;
        bfs.pop();
        for(int e : g[u]){
            if(mark[e]) continue;
            mark[e] = 1;
            bfs.push(e);
        }
    }
    if(cnt == m) return 0;
    return 1;
}

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