Submission #578625

#	Time	Username	Problem	Language	Result	Execution time	Memory
578625		jasmin	Roller Coaster Railroad (IOI16_railroad)	C++17	30 / 100	1451 ms	126076 KiB

railroad

#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
#define int long long

const int inf=1e18;

int dfs(int v, map<int, vector<int> >& adi, map<int, bool>& vis){
    //cout << v << "\n";
    if(vis[v]) return 0;
    vis[v]=true;

    int cnt=1;
    for(auto u: adi[v]){
        cnt+=dfs(u, adi, vis);
    }
    return cnt;
}

bool connected(int n, int start, map<int, vector<int> >& adi){
    map<int, bool> vis;
    return dfs(start, adi, vis)==n;
}

int plan_roller_coaster(vector<int32_t> s, vector<int32_t> t){
    int n=s.size();
    
    map<int, vector<int> > adi;
    vector<pair<int, int> > time;
    for(int i=0; i<n; i++){
        adi[s[i]].push_back(t[i]);
        adi[t[i]].push_back(s[i]); 
        
        time.push_back({s[i], 1});
        time.push_back({t[i], -1});
    }
    sort(time.begin(), time.end());

    bool pos=true;
    int sum=-1;
    int dif=1;
    for(int i=0; i<(int)time.size(); i++){
        if(0<i && time[i-1].first!=time[i].first){
            dif++;
        }

        sum+=time[i].second;
        if(sum>0) pos=false;

        if(sum<0 && i+1<(int)time.size()){
            adi[time[i].first].push_back(time[i+1].first);
            adi[time[i+1].first].push_back(time[i].first);
        }
    }

    //cout << pos << " " << dif << "\n";

    if(pos && connected(dif, s[0], adi)){
        return 0;
    }
    return 1;
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int32_t> s(n);
    vector<int32_t> t(n);
    for(int i=0; i<n; i++){
        cin >> s[i];
    }
    for(int i=0; i<n; i++){
        cin >> t[i];
    }
    cout << plan_roller_coaster(s, t) << "\n";
}*/

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