Submission #223606

#	Time	Username	Problem	Language	Result	Execution time	Memory
223606		DavidDamian	Roller Coaster Railroad (IOI16_railroad)	C++11	64 / 100	137 ms	15336 KiB

railroad

//#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
///Subtask 3
///Disjoint Sets
///Sweep Line
///Just check if every time the sum is <=0 and all the special sections are connected
ll cost[17][17];
ll memo[100005][17];
int link[200005];
int setSize[200005];
int Find(int u)
{
    if(link[u]==u) return u;
    else return link[u]=Find(link[u]);
}
bool same(int u,int v)
{
    return Find(u)==Find(v);
}
void unite(int u,int v)
{
    u=Find(u);
    v=Find(v);
    if(u==v) return;
    if(setSize[v]>setSize[u]) swap(u,v);
    setSize[u]+=setSize[v];
    link[v]=u;
}
void initDSU(int n)
{
    for(int i=1;i<=n;i++){
        setSize[i]=1;
        link[i]=i;
    }
}
struct event
{
    int T;
    int op;
    int id; //Which special section
    bool operator<(const event& a)
    {
        if(T<a.T) return true;
        else{
            if(T==a.T){
                if(op<a.op) return true;
                else return false;
            }
            else return false;
        }
    }
};
vector<event> timeline;
long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int n=s.size();
    if(n<=16){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(j==i) continue;
                cost[i][j]=max(0,t[i]-s[j]);
            }
        }
        for(ll m=3;m<=(1<<n)-1;m++){
            for(int i=0;i<n;i++){
                if(m & (1<<i)){
                    if(m == (1<<i)){
                        memo[m][i]=0;
                        continue;
                    }
                    memo[m][i]=LLONG_MAX;
                    ll before_m=m-(1<<i);
                    for(int j=0;j<n;j++){
                        if(j==i) continue;
                        if(before_m & (1<<j))
                            memo[m][i]=min(memo[m][i],memo[before_m][j]+cost[j][i]);
                    }
                }
            }
        }
        ll minimum=LLONG_MAX;
        for(int i=0;i<n;i++){
            minimum=min(minimum,memo[(1<<n)-1][i]);
        }
        return minimum;
    }

    initDSU(n);
    for(int i=0;i<n;i++){
        event e={s[i],+1,i+1};
        timeline.push_back(e);
        e={t[i],-1,i+1};
        timeline.push_back(e);
    }
    sort(timeline.begin(),timeline.end());
    //Lines to the right are +1
    //Lines to the left are -1
    int balance=-1; //Because there is a line that goes from inf to 1
    for(int i=0;i<2*n-1;i++){
        balance+=timeline[i].op;
        if(balance<0){
            unite(timeline[i].id,timeline[i+1].id);
        }
        else if(balance>0){
            return 1; //Not possible with 0, we need to add tracks to slow down
        }
    }
    int root=Find(1);
    for(int i=1;i<=n;i++){
        if(Find(i)!=root)
            return 1; //Not possible with 0, the sections are not fully connected
    }
    return 0;
}

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