Submission #1142739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142739		anmattroi	Dreaming (IOI13_dreaming)	C++17	100 / 100	81 ms	25032 KiB

dreaming

/**********************************************

Task: IOI13_DREAMING
Link: https://oj.uz/problem/view/IOI13_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);
    }

    int ans = 0;
    vector<int> r;
    for (int i = 0; i < n; i++) if (!cl[i]) {
        ii x = Find_best(i);
        r.emplace_back(x.fi);
        cmax(ans, x.se);
    }



    sort(r.begin(), r.end());
    reverse(r.begin(), r.end());

    if (r.size() == 2) cmax(ans, r[0]+r[1]+l);
    else if (r.size() >= 3) {
        cmax(ans, r[0]+r[1]+l);
        cmax(ans, r[1]+r[2]+2*l);
    }
    return ans;
}
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/
//18

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