Submission #617803

#	Time	Username	Problem	Language	Result	Execution time	Memory
617803		Drew_	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	224 ms	19764 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second
#define size(x) (int)x.size()

using ll = long long;
using ii = pair<int, int>;

const ll inf = 1e18 + 69;


namespace sub1
{
    ll solve(vector<int> s,vector<int> t)
    {
        int n = size(s);
        vector<ii> v(n);
        for (int i = 0; i < n; ++i)
            v[i] = {s[i], t[i]};
        sort(v.begin(), v.end());

        ll mn = inf;
        do
        {
            ll ctr = 0;
            for (int i = 0, cur = 1; i < n; ++i)
            {
                ctr += max(0, cur - v[i].f1);
                cur = v[i].s2;
            }
            mn = min(mn, ctr);

            if (ctr == 8)
            {
                for (auto [l, r] : v)
                    cout << l << " " << r << " -- ";
                cout << '\n';
                for (auto [l, r] : v) if (l < r)
                    cout << l << " " << r << " __ ";
                cout << '\n';
                for (auto [l, r] : v) if (l >= r)
                    cout << l << " " << r << " -- ";
                cout << "\n\n";
            }

        } while (next_permutation(v.begin(), v.end()));
        return mn;
    }
}

namespace sub2
{
    ll solve(vector<int> s, vector<int> t)
    {
        int N = size(s);
        vector<vector<ll>> dp(N, vector<ll>(1 << N, inf));
        const auto rc = [&](const auto &self, int id, int mask) -> ll
        {
            if (mask == (1 << N) - 1)
                return 0;
            if (dp[id][mask] != inf)
                return dp[id][mask];
            for (int i = 0; i < N; ++i) if (~mask >> i & 1)
                dp[id][mask] = min(dp[id][mask], max(0, t[id] - s[i]) + self(self, i, mask | (1 << i)));
            return dp[id][mask];
        };

        ll res = inf;
        for (int i = 0; i < N; ++i)
            res = min(res, rc(rc, i, 1 << i));
        return res;
    }
}  

namespace full
{
    const int MAX = 4e5 + 69;

    int ds[MAX];
    inline int frep(int x) { return ds[x] == x ? x : ds[x] = frep(ds[x]); }
    inline void join(int x, int y) { ds[frep(x)] = frep(y); }

    ll solve(vector<int> s, vector<int> t)
    {
        int n = size(s);

        vector<int> zip = {};
        for (int x : s)
            zip.pb(x);
        for (int x : t)
            zip.pb(x);

        sort(zip.begin(), zip.end());
        zip.resize(unique(zip.begin(), zip.end()) - zip.begin());
        for (int &x : s)
            x = (int)(lower_bound(zip.begin(), zip.end(), x) - zip.begin());
        for (int &x : t)
            x = (int)(lower_bound(zip.begin(), zip.end(), x) - zip.begin());

        vector<ll> pfx(size(zip), 0);
        
        pfx[0]--;
        for (int i = 0; i < n; ++i)
            pfx[s[i]]++, pfx[t[i]]--;
        for (int i = 1; i < size(zip); ++i)
            pfx[i] += pfx[i-1];

        ll res = 0;
        for (int i = 0; i+1 < size(zip); ++i)
            res += max(0ll, pfx[i]) * (zip[i+1] - zip[i]);

        iota(ds, ds + MAX, 0);
        for (int i = 0; i < n; ++i)
            join(s[i], t[i]);
        for (int i = 0; i+1 < size(zip); ++i)
        {
            if (pfx[i])
                join(i, i+1);
        }

        vector<array<int, 3>> edges;
        for (int i = 0; i+1 < size(zip); ++i)
        {
            if (frep(i) != frep(i+1))
                edges.pb({zip[i+1] - zip[i], frep(i), frep(i+1)});
        }
        sort(edges.begin(), edges.end());

        for (auto [w, u, v] : edges)
        {
            if (frep(u) != frep(v))
                join(u, v), res += w;
        }

        return res;
    }
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    return full :: solve(s, t);
}

// int main() {
//     mt19937 RNG(69);
//     const auto randint = [&](int l, int r) -> int
//     {
//         return uniform_int_distribution<int>(l, r)(RNG);
//     };

//     for (int rep = 0; rep < 100; ++rep)
//     {
//         cerr << "rep " << rep << '\n';

//         int n = 16;
//         vector<int> s(n), t(n);
//         for (int i = 0; i < n; ++i)
//             s[i] = randint(1, 10), t[i] = randint(1, 10);

//         int ans = full :: solve(s, t);
//         int key = sub2 :: solve(s, t);
//         if (ans != key)
//         {
//             cout << ans << " and " << key << "\n\n";
//             cout << n << '\n';
//             for (int i = 0; i < n; ++i)
//                 cout << s[i] << " " << t[i] << '\n';
//             return 0;
//         }
//     }
//     return 0;
// }

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