Submission #607158

#	Time	Username	Problem	Language	Result	Execution time	Memory
607158		Koosha_mv	Roller Coaster Railroad (IOI16_railroad)	C++14	64 / 100	424 ms	104368 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,int(v.size())) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=1e6+99,inf=1e9+99;

int n,m,cnt,in[N],out[N],vis[N];
ll dp[(1<<18)][18];
vector<int> ga[N],gb[N];

void reset(){
    cnt=0;
    f(i,0,n) vis[i]=0;
}
void add(int u,int v,int t){
    //cout<<u<<" "<<v<<" -> "<<t<<endl;
    in[v]+=t;
    out[u]+=t;
    ga[u].pb(v);
    gb[v].pb(u);
}
void dfs(int u,vector<int> *g){
    cnt++;
    vis[u]=1;
    for(auto v : g[u]){
        if(vis[v]==1) continue ;
        dfs(v,g);
    }
}

ll plan_roller_coaster(vector<int> s,vector<int> t) {
    m=s.size();
    if(s.size()<17){
        m++;
        s.pb(0);
        t.pb(0);
        f(mask,0,(1<<m)) f(i,0,m) dp[mask][i]=1ll*inf*N;
        dp[(1<<(m-1))][m-1]=0;
        f(mask,1,(1<<m)){
            f(i,0,m){
                if(bit(mask,i)==0) continue ;
                f(j,0,m){
                    if(bit(mask,j)==1) continue ;
                    minm(dp[mask^(1<<j)][j],dp[mask][i]+max(0ll,1ll*t[i]-s[j]));
                }
            }
        }
        ll ans=1ll*inf*N;
        f(i,0,m) minm(ans,dp[(1<<m)-1][i]);
        return ans;
    }
    vector<int> vec;
    vec.pb(0);
    vec.pb(inf);
    f(i,0,s.size()) vec.pb(s[i]),vec.pb(t[i]);
    sort(all(vec));
    vec.resize(unique(all(vec))-vec.begin());
    n=vec.size();
    f(i,0,s.size()){
        int u=lower_bound(all(vec),s[i])-vec.begin(),v=lower_bound(all(vec),t[i])-vec.begin();
        add(u,v,1);
    }
    add(n-1,0,1);
    f(i,0,n-1){
        if(in[i]<out[i]) return 1;
        if(in[i]>out[i]){
            add(i,i+1,in[i]-out[i]);
        }
    }
    f(i,0,n){
        //cout<<in[i]<<" - "<<out[i]<<endl;
    }
    reset();
    dfs(0,ga);
    if(cnt<n) return 1;
    reset();
    dfs(0,gb);
    if(cnt<n) return 1;
    return 0;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   74 |     f(i,0,s.size()) vec.pb(s[i]),vec.pb(t[i]);
      |       ~~~~~~~~~~~~             
railroad.cpp:74:5: note: in expansion of macro 'f'
   74 |     f(i,0,s.size()) vec.pb(s[i]),vec.pb(t[i]);
      |     ^
railroad.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   78 |     f(i,0,s.size()){
      |       ~~~~~~~~~~~~             
railroad.cpp:78:5: note: in expansion of macro 'f'
   78 |     f(i,0,s.size()){
      |     ^

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