Submission #121272

#	Time	Username	Problem	Language	Result	Execution time	Memory
121272		sealnot123	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	2021 ms	25132 KiB

railroad

#ifdef LOCAL
#include "grader.cpp"
#endif

#include "railroad.h"
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
int n;
LL dp[16][1<<16], edge[16][16];
struct A{
    LL w;
    int u, b;
    bool operator <(const A& o) const{
        return w>o.w;
    }
};
priority_queue<A> dijk;
LL plan_roller_coaster(vector<int> s, vector<int> t) {
    n = SZ(s);
    int i,j;
    for(i=0;i<n;i++){
        for(j=0;j<(1<<n);j++) dp[i][j] = 1e18;
    }
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            if(i==j) edge[i][j] = 0;
            else edge[i][j] = max(0, t[i]-s[j]);
        }
    }
    for(i=0;i<n;i++){
        dp[i][1<<i] = 0;
        dijk.push({0, i, 1<<i});
    }
    while(!dijk.empty()){
        int u = dijk.top().u;
        LL w = dijk.top().w;
        int b = dijk.top().b;
        dijk.pop();
        for(i=0;i<n;i++){
            if(i==u || (b&(1<<i))) continue;
            if(dp[i][b|(1<<i)] > w + edge[u][i]){
                dp[i][b|(1<<i)] = w + edge[u][i];
                dijk.push({dp[i][b|(1<<i)], i, b|(1<<i)});
            }
        }
    }
    LL ans = 1e18;
    for(i=0;i<n;i++) ans = min(ans, dp[i][(1<<n)-1]);
    return ans;
}

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