Submission #1156623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156623		Esgeer	Dreaming (IOI13_dreaming)	C++20	47 / 100	95 ms	16060 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    #pragma GCC target("avx2")
#endif
#define int long long
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define vb vector<bool>
#define vvb vector<vb>
#define endl '\n'
#define sp <<' '<<
#define F(i, s, n) for(int i = s; i < (int) n; i++)
#define pb push_back
#define fi first
#define se second

const int N = 1e5+5;
const int inf = 1e18;

vpi adj[N];
vvi trees;
bool vis1[N];
int dep1[N], dep2[N];
void get_tree(int node, int par, vector<int> *list) {
    vis1[node] = 1;
    list->pb(node);
    for(auto &go : adj[node]) if(go.fi != par) get_tree(go.fi, node, list);
}
int dep_dfs1(int node, int par, int dep = 0) {
    dep1[node] = dep;
    int ans = node;
    for(auto &go : adj[node]) if(go.fi != par) {
        int chans = dep_dfs1(go.fi, node, dep + go.se);
        if(dep1[chans] > dep1[ans]) ans = chans;
    }
    return ans;
}
int dep_dfs2(int node, int par, int dep = 0) {
    dep2[node] = dep;
    int ans = node;
    for(auto &go : adj[node]) if(go.fi != par) {
        int chans = dep_dfs2(go.fi, node, dep + go.se);
        if(dep2[chans] > dep2[ans]) ans = chans;
    }
    return ans;
}

int32_t travelTime(int32_t N, int32_t M, int32_t L, int32_t A[], int32_t B[], int32_t T[]) {
    F(i, 0, M) {
        adj[A[i]].pb({B[i], T[i]});
        adj[B[i]].pb({A[i], T[i]});
    }

    F(i, 0, N) {
        if(vis1[i]) continue;
        trees.pb({});
        get_tree(i, i, &trees.back());
    }

    vi tree_lengths;

    int ans_from_inner_tree = 0;

    for(vector<int> &tree : trees) {
        int diameter1 = dep_dfs1(tree[0], -1);
        int diameter2 = dep_dfs2(diameter1, -1);
        dep_dfs1(diameter2, -1);

        int bestLeader = inf;
        for(int node : tree) {
            bestLeader = min(bestLeader, max(dep1[node], dep2[node]));
        }

        ans_from_inner_tree = max(ans_from_inner_tree, dep1[diameter1]);

        tree_lengths.pb(bestLeader);
    }

    sort(tree_lengths.begin(), tree_lengths.end(), greater<int>());

    if(trees.size() == 1) {
        return ans_from_inner_tree;
    } else if(trees.size() == 2) {
        return max(ans_from_inner_tree, tree_lengths[0] + tree_lengths[1] + L);
    } else {
        return max({ans_from_inner_tree, tree_lengths[0] + tree_lengths[1] + L, tree_lengths[0] + tree_lengths[2] + L * 2});
    }

    return 31837837; // let LEBLEBIE do its magic ♦
}

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