Submission #1207408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207408		SansPapyrus683	Dreaming (IOI13_dreaming)	C++20	100 / 100	64 ms	27328 KiB

dreaming

#include <bits/stdc++.h>

#if __has_include("dreaming.h")
#include "dreaming.h"
#endif

#if __has_include("debugging.hpp")
#include "debugging.hpp"
#endif
using namespace std;

class Tree {
   private:
    vector<vector<pair<int, int>>> neighbors;
    vector<pair<int, int>> farthest;
    vector<pair<int, int>> second_farthest;
    vector<int> curr_comp;

    void fill_farthest_inside(int at, int prev) {
        curr_comp.push_back(at);
        vector<pair<int, int>> dists;
        for (const auto& [n, dist] : neighbors[at]) {
            if (n != prev) {
                fill_farthest_inside(n, at);
                dists.push_back({farthest[n].first + dist, n});
            }
        }
        std::sort(dists.begin(), dists.end(), std::greater<pair<int, int>>());
        farthest[at] = dists.size() >= 1 ? dists[0] : pair<int, int>{0, -1};
        second_farthest[at] = dists.size() >= 2 ? dists[1] : pair<int, int>{0, -1};
    }

    void fill_farthest(int at, int prev, int dist) {
        if (dist != -1) {
            pair<int, int> prev_path =
                (farthest[prev].second != at ? farthest : second_farthest)[prev];
            if (farthest[at].first < prev_path.first + dist) {
                farthest[at] = {prev_path.first + dist, prev};
            } else if (second_farthest[at].first < prev_path.first + dist) {
                second_farthest[at] = {prev_path.first + dist, prev};
            }
        }
        for (const auto& [n, dist] : neighbors[at]) {
            if (n != prev) { fill_farthest(n, at, dist); }
        }
    }

   public:
    vector<vector<int>> comps;  // cba to pound out getters or whatever

    Tree(const vector<vector<pair<int, int>>>& neighbors)
        : neighbors(neighbors),
          farthest(neighbors.size(), {-1, -1}),
          second_farthest(neighbors.size()) {
        for (int i = 0; i < neighbors.size(); i++) {
            if (farthest[i] == make_pair(-1, -1)) {
                curr_comp = {};
                fill_farthest_inside(i, i);
                fill_farthest(i, i, -1);
                comps.push_back(curr_comp);
            }
        }
    }

    int longest_path(int n) { return farthest[n].first; }
};

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    vector<vector<pair<int, int>>> adj(n);
    for (int i = 0; i < m; i++) {
        adj[a[i]].push_back({b[i], t[i]});
        adj[b[i]].push_back({a[i], t[i]});
    }
    Tree tree(adj);

    vector<int> worst;
    int baseline = INT32_MIN;
    for (const vector<int>& c : tree.comps) {
        int farthest = INT32_MAX;
        for (int i : c) {
            farthest = min(farthest, tree.longest_path(i));
            baseline = max(baseline, tree.longest_path(i));
        }
        worst.push_back(farthest);
    }
    sort(worst.begin(), worst.end());

    int w = worst.size();
    if (w == 1) {
        return baseline;
    } else if (w == 2) {
        return max(worst[0] + l + worst[1], baseline);
    }

    int to_hub = worst[w - 2] + l + worst[w - 1];
    int otherwise = worst[w - 3] + 2 * l + worst[w - 2];
    return max(to_hub, max(otherwise, baseline));
}

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