제출 #1029331

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1029331		c2zi6	Roller Coaster Railroad (IOI16_railroad)	C++14	64 / 100	493 ms	68416 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;
    }
};
namespace TEST3 {
    int n;
    VVI gp;
    VVI trans;
    VI vis;
    void dfs(int u) {
        vis[u] = true;
        for (int v : gp[u]) if (!vis[v]) dfs(v);
        for (int v : trans[u]) if (!vis[v]) dfs(v);
    }
    ll solve(VI U, VI V) {
        {/* 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++;
            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 extra(n);
        {/* filter non-eulerian graphs */
            VI a(n);
            rep(u, n) a[u] = gp[u].size() - trans[u].size();
            stack<int> st;
            rep(u, n) {
                int cnt = abs(a[u]);
                if (a[u] < 0) {
                    while (cnt--) st.push(u);
                } else if (a[u] > 0) {
                    while (cnt--) {
                        if (st.size() == 0) return 1;
                        /*cout << "LONG EDGE: " << st.top() << " " << u << endl;*/
                        extra[st.top()]++;
                        extra[u]--;
                        st.pop();
                    }
                }
            }
            if (st.size()) return 1;
        }
        replr(i, 1, n) extra[i] += extra[i-1];
        rep(i, n-1) if (extra[i]) {
            gp[i].pb(i+1);
            trans[i+1].pb(i);
            /*cout << "DECOMPOSED: " << i << " " << i+1 << endl;*/
        }
        vis = VI(n);
        dfs(0);
        rep(u, n) if (!vis[u]) return 2;
        return 0;
    }
};

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 = 10000;
    int n = 10;
    int m = 2*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 ((bool)TEST2::solve(a, b) != (bool)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;
}

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