Submission #1295272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295272		trandangquang	Roller Coaster Railroad (IOI16_railroad)	C++20	34 / 100	470 ms	589824 KiB

railroad

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

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define fi first
#define se second
#define ll long long
#define eb emplace_back
#define pb push_back
#define __builtin_popcount __builtin_popcountll
#define _ << " " <<

template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}

const int N=2e5+5;
const int INF=1e9;

int n,bal[N],p[N]; ll res=0;
vi rar;

int find(int x){
    return p[x]==x ? x : p[x]=find(p[x]);
}
bool unite(int x, int y){
    x=find(x); y=find(y);
    if(x!=y){
        p[y]=x;
        return true;
    }
    return false;
}

ll plan_roller_coaster(vi s, vi t) {
    s.eb(INF), t.eb(1);

    n=sz(s);
    rep(i,n) rar.eb(s[i]), rar.eb(t[i]);

    sort(all(rar));
    rar.erase(unique(all(rar)),rar.end());
    rep(i,n){
        s[i]=lower_bound(all(rar),s[i])-rar.begin();
        t[i]=lower_bound(all(rar),t[i])-rar.begin();
    }

    iota(p,p+sz(rar),0);
    rep(i,n){
        bal[s[i]]++; bal[t[i]]--;
        unite(s[i],t[i]);
    }
    rep(i,sz(rar)){
        if(i>0) bal[i]+=bal[i-1];
        if(bal[i]!=0){ /// must have edge which go through this (greedy here to connect these)
            unite(i,i+1);
            res+=max(0LL,1LL*(rar[i+1]-rar[i])*bal[i]);
        }
    }

    vector<pair<int,ii>> eds;
    rep(i,sz(rar)-1){
        if(find(i)!=find(i+1)){
            eds.pb({rar[i+1]-rar[i],{i,i+1}});
        }
    }
    sort(all(eds));
    for(pair<int,ii> e:eds){
        if(unite(e.se.fi,e.se.se)){
            res+=e.fi;
        }
    }
    return res;
}

Compilation message (stderr)

railroad.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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