제출 #578627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
578627		jasmin	Roller Coaster Railroad (IOI16_railroad)	C++17	64 / 100	1495 ms	130028 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){
    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 find_dp(int mask, int x, vector<vector<int> >& dp, vector<int32_t>& s, vector<int32_t>& t, int n){
    if(dp[mask][x]!=inf) return dp[mask][x];

    for(int i=0; i<n; i++){
        if(i==x || (mask>>i)%2!=1) continue;
        dp[mask][x]=min(dp[mask][x], find_dp(mask-(1<<x), i, dp, s, t, n)+max(0, t[x]-s[i]));
    }
    return dp[mask][x];
}

int plan_roller_coaster_bitmask(vector<int32_t> s, vector<int32_t> t){
    int n=s.size();
    int pow2=(1<<n);

    vector<vector<int> > dp(pow2, vector<int> (n, inf));
    for(int i=0; i<n; i++){
        dp[(1<<i)][i]=0;
    }
    int ans=inf;
    for(int i=0; i<n; i++){
        ans=min(ans, find_dp(pow2-1, i, dp, s, t, n));
    }
    return ans;
}

int plan_roller_coaster(vector<int32_t> s, vector<int32_t> t){
    int n=s.size();
    if(n<=16){
        return plan_roller_coaster_bitmask(s, t);
    }

    
    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);
        }
    }

    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: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 30 / 30
• Subtask 4: 0 / 36