Submission #471576

#	Time	Username	Problem	Language	Result	Execution time	Memory
471576		jalsol	Dreaming (IOI13_dreaming)	C++17	100 / 100	99 ms	17392 KiB

dreaming

// looking to shine brighter in this world...

#define TASK "dreaming"
#include "dreaming.h"

#ifdef LOCAL
#include "local.h"
#else
#include <bits/stdc++.h>
#define debug(...)
#define DB(...)
#endif

using namespace std;

using ll = long long;
using ld = long double;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)
#define Fe(...) for (auto __VA_ARGS__)

template <class C> inline int isz(const C& c) { return static_cast<int>(c.size()); }
template <class T> inline bool chmin(T& a, const T& b) { return (a > b) ? a = b, true : false; }
template <class T> inline bool chmax(T& a, const T& b) { return (a < b) ? a = b, true : false; }

const bool __initialization = []() {
    cin.tie(nullptr)->sync_with_stdio(false);
    if (fopen(TASK".inp", "r")) {
        (void)(!freopen(TASK".inp", "r", stdin));
        (void)(!freopen(TASK".out", "w", stdout)); }
    cout << setprecision(12) << fixed;
    return true;
}();

constexpr ld eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// ================================================================================

// thanks to my aniki tht2005 for explaining

constexpr int maxn = 1e5 + 5;

struct Edge { int v, c; };

int n, ne, cost;
vector<Edge> g[maxn];

int vis[maxn];
int timer;

int dp1[maxn];

void DfsDown(int u, int p) {
    vis[u] = timer;

    Fe (&[v, c] : g[u]) {
        if (v == p) continue;
        DfsDown(v, u);
        chmax(dp1[u], dp1[v] + c);
    }
}

int dp2[maxn];

void DfsUp(int u, int p) {
    int fi = -1, se = -1;

    Fe (&[v, c] : g[u]) {
        if (v == p) continue;

        if (fi < dp1[v] + c) {
            tie(fi, se) = pair(dp1[v] + c, fi);
        }
        else {
            chmax(se, dp1[v] + c);
        }
    }

    Fe (&[v, c] : g[u]) {
        if (v == p) continue;

        dp2[v] = dp2[u] + c;

        if (fi == dp1[v] + c) {
            chmax(dp2[v], se + c);
        }
        else {
            chmax(dp2[v], fi + c);
        }

        DfsUp(v, u);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    { n = N; ne = M; cost = L; }

    Rep (i, ne) {
        int u = A[i], v = B[i], c = T[i];
        g[u].push_back({ v, c });
        g[v].push_back({ u, c });
    }

    Rep (u, n) {
        if (!vis[u]) {
            ++timer;
            DfsDown(u, -1);
            DfsUp(u, -1);
        }
    }

    Rep (u, n) chmax(dp1[u], dp2[u]);

    vector<int> a(timer + 1, inf);
    Rep (u, n) chmin(a[vis[u]], dp1[u]);

    dp1[n] = [&a, L]() {
        if (timer == 1) return a[1];
        if (timer == 2) return a[1] + a[2] + L;

        sort(1 + all(a), greater<int>());
        int ret = inf;
        array<array<int, 3>, 3> perm {{
            {{ 1, 2, 3 }},
            {{ 2, 1, 3 }},
            {{ 3, 1, 2 }}
        }};

        Fe (&[x, y, z] : perm) {
            int get = max({
                a[x] + a[y] + L,
                a[x] + a[z] + L,
                a[y] + a[z] + 2 * L
            });
            chmin(ret, get);
        }

        return ret;
    }();

    return *max_element(dp1, dp1 + n + 1);
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23