Submission #1029346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029346		c2zi6	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	513 ms	66836 KiB

railroad

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "railroad.h"

namespace TEST2 {
    const int MAXN = 16;
    ll dp[1<<MAXN][MAXN];
    ll solve(VI a, VI b) {
        int n = a.size();
        rep(s, 1<<n) rep(i, n) if (s & (1<<i)) {
            int st = (s^(1<<i));
            if (st == 0) {
                dp[s][i] = 0;
            } else {
                dp[s][i] = 1e18;
                rep(j, n) if (st & (1<<j)) {
                    setmin(dp[s][i], dp[st][j] + max(0, b[j]-a[i]));
                }
            }
        }
        ll ans = 1e18;
        rep(i, n) setmin(ans, dp[(1<<n)-1][i]);
        return ans;
    }
};

struct DSU {
    VI par;
    VI cnt;
    DSU(int n) {
        par = cnt = VI(n);
        rep(i, n) {
            par[i] = i;
            cnt[i] = 1;
        }
    }
    int get(int u) {
        if (u == par[u]) return u;
        return par[u] = get(par[u]);
    }
    bool join(int u, int v) {
        u = get(u);
        v = get(v);
        if (u == v) return false;
        if (cnt[v] > cnt[u]) swap(u, v);
        cnt[u] += cnt[v];
        par[v] = u;
        return true;
    }
};

namespace TEST3 {
    int n;
    VVI gp;
    VVI trans;
    ll solve(VI U, VI V) {
        VI val;
        {/* compress */
            map<int, int> ind;
            rep(i, U.size()) ind[U[i]] = ind[V[i]] = 0;
            n = 0;
            for (auto& p : ind) {
                p.ss = n++;
                val.pb(p.ff);
            }
            rep(i, U.size()) {
                U[i] = ind[U[i]];
                V[i] = ind[V[i]];
            }
        }
        if (n == 1) return 0;
        gp = trans = VVI(n);
        rep(i, U.size()) {
            gp[U[i]].pb(V[i]);
            trans[V[i]].pb(U[i]);
        }
        gp[n-1].pb(0);
        trans[0].pb(n-1);
        VI extradown(n);
        VI extraup(n);
        ll ans = 0;
        {/* add edges to make graph eulerian */
            VI a(n);
            rep(u, n) a[u] = gp[u].size() - trans[u].size();
            stack<int> pos;
            stack<int> neg;
            rep(u, n) {
                int cnt = abs(a[u]);
                if (a[u] < 0) {
                    while (cnt && pos.size()) {
                        ans += val[u] - val[pos.top()];
                        /*cout << u << " " << pos.top() << endl;*/
                        extraup[pos.top()]++;
                        extraup[u]--;
                        pos.pop();
                        cnt--;
                    }
                    while (cnt--) {
                        neg.push(u);
                    }
                } else if (a[u] > 0) {
                    while (cnt && neg.size()) {
                        /*cout << neg.top() << " " << u << endl;*/
                        extradown[neg.top()]++;
                        extradown[u]--;
                        neg.pop();
                        cnt--;
                    }
                    while (cnt--) {
                        pos.push(u);
                    }
                }
            }
        }
        replr(i, 1, n) {
            extradown[i] += extradown[i-1];
            extraup[i] += extraup[i-1];
        }
        rep(i, n-1) {
            if (extraup[i]) {
                gp[i].pb(i+1);
                trans[i+1].pb(i);
                /*cout << "DECOMPOSED: " << i << " " << i+1 << endl;*/
            }
            if (extradown[i]) {
                gp[i+1].pb(i);
                trans[i].pb(i+1);
                /*cout << "DECOMPOSED: " << i+1 << " " << i << endl;*/
            }
        }
        DSU dsu(n);
        rep(u, n) for (int v : gp[u]) {
            dsu.join(u, v);
        }
        VPI edges;
        rep(i, n-1) edges.pb({val[i+1]-val[i], i});
        sort(all(edges));
        for (auto[w, u] : edges) {
            if (dsu.join(u, u+1)) {
                ans += w;
            }
        }
        return ans;
    }
};

ll plan_roller_coaster(VI a, VI b) {
    if (a.size() <= 16) return TEST2::solve(a, b);
    return TEST3::solve(a, b);
    srand(time(0));
    int t = 1000;
    int n = 10;
    int m = 4*n;
    while (t--) {
        cout << "counter: " << t << endl;
        a = b = VI(n);
        rep(i, n) {
            a[i] = rand()%m+1;
            b[i] = rand()%m+1;
        }
        if (TEST2::solve(a, b) != TEST3::solve(a, b)) {
            cout << "VERJAPES" << endl;
            rep(i, n) {
                cout << a[i] << " " << b[i] << endl;
            }
            cout << "asnwers: " << TEST2::solve(a, b) << " " << TEST3::solve(a, b) << endl;
            return 0;
        }
    }
    return 0;
}

Compilation message (stderr)

railroad.cpp: In function 'll TEST3::solve(VI, VI)':
railroad.cpp:167:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  167 |         for (auto[w, u] : edges) {
      |                  ^

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