Submission #1138346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138346		anmattroi	꿈 (IOI13_dreaming)	C++17	47 / 100	55 ms	25032 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define maxn 100005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

inline constexpr void cmax(int &x, const int &y) {if (x < y) x = y;}
inline constexpr void cmin(int &x, const int &y) {if (x > y) x = y;}

inline constexpr void best(ii &x, const int &y) {
    if (x.fi < y) {
        x.se = x.fi;
        x.fi = y;
    } else if (x.se < y) x.se = y;
}

int n, m, l;

struct edge {
    int u, v, l;
    edge() {}
    edge(int _u, int _v, int _l) : u(_u), v(_v), l(_l) {}
} edges[maxn];

int cl[maxn];
int d[maxn];
ii f[maxn]; int g[maxn];

vector<ii> adj[maxn];

ii Find_best(int z) {
    vector<int> nodes;

    function<void(int, int)> dfs = [&](int u, int dad) {
        cl[u] = 1;
        nodes.emplace_back(u);
        for (auto [v, l] : adj[u])
        if (v != dad) {
            d[v] = d[u] + l;
            dfs(v, u);
            best(f[u], f[v].fi+l);
        }
    };

    function<void(int, int)> tfs = [&](int u, int dad) {
        for (auto [v, l] : adj[u])
        if (v != dad) {
            if (f[u].fi == f[v].fi+l) g[v] = max(g[u], f[u].se) + l;
            else g[v] = max(g[u], f[u].fi) + l;
            tfs(v, u);
        }
    };

    ii cr = {INT_MAX, -1};

    dfs(z, 0); tfs(z, 0);

    int opt = 0;

    for (int i : nodes) {
        if (cr.se < d[i]) {
            cr.se = d[i];
            opt = i;
        }
        cmin(cr.fi, max(f[i].fi, g[i]));
    }
    d[opt] = 0;
    dfs(opt, 0);
    for (int i : nodes) cmax(cr.se, d[i]);
    return cr;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n = N; m = M; l = L;
    for (int i = 0; i < m; i++) edges[i] = edge(A[i], B[i], T[i]);
    for (int i = 0; i < n; i++) {
        cl[i] = g[i] = d[i] = 0;
        adj[i].clear();
    }
    for (int i = 0; i < m; i++) {
        auto [u, v, l] = edges[i];
        adj[u].emplace_back(v, l);
        adj[v].emplace_back(u, l);
    }

    //Optimal point.. diameter.. ok that's it
    multiset<ii> q;
    for (int i = 0; i < n; i++) if (!cl[i]) q.insert(Find_best(i));



    while (q.size() > 1) {
        auto it = q.begin();
        ii H1 = *it; ++it;
        ii H2 = *it;
        q.erase(q.find(H1));
        q.erase(q.find(H2));


        q.insert(ii{
                 min(max(H1.fi, H2.fi+l), max(H1.fi+l, H2.fi)),
                 max({H1.se, H2.se, l + H1.fi + H2.fi})});

    }

    return q.begin()->se;
}

//18

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