Submission #573056

#	Time	Username	Problem	Language	Result	Execution time	Memory
573056		2fat2code	Roller Coaster Railroad (IOI16_railroad)	C++17	30 / 100	862 ms	91328 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
#define rc(s) return cout << s, 0
using namespace std;
 
const int nmax = 400005;
 
int n;
unordered_map<int,vector<int>>mp_in;
unordered_map<int,vector<int>>mp_out;
vector<int>compress;
bitset<nmax>viz;
 
void dfs(int s){
   // cout << "CHECK " << s << '\n';
    viz[s] = 1;
    for(auto it : mp_out[compress[s]]){
        auto it2 = lower_bound(all(compress), it) - compress.begin();
        if(!viz[it2]) dfs(it2);
    }
}
 
long long plan_roller_coaster(vector<int> s, vector<int> t) {
    s.push_back(2 * 1e9);
    t.push_back(1);
    n = (int)s.size();
    for(int i=0;i<n;i++){
        mp_out[s[i]].push_back(t[i]);
        mp_in[t[i]].push_back(s[i]);
        compress.push_back(s[i]);
        compress.push_back(t[i]);
    }
    sort(all(compress));
    compress.resize(unique(all(compress)) - compress.begin());
    int curr = 0;
    for(int i=0;i<(int)compress.size();i++){
        auto it = compress[i];
        if(curr > 0) mp_out[compress[i-1]].push_back(compress[i]);
        int x = mp_out[it].size() - mp_in[it].size();
     //   cout << i << ' ' << x << '\n';
        if(x > 0){
            curr -= x;
            if(curr < 0) return 1;
        }
        else if(x < 0){
            curr += abs(x);
        }
    }
   // if(curr > 0) return 1;
    //cout << "CHECK " << '\n';
    dfs(0);
    if(viz.count() != compress.size()) return 1;
    return 0;
}
 
// 1. Solve the problem
// 2. ???
// 3. Profit

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