Submission #1207405

#TimeUsernameProblemLanguageResultExecution timeMemory
1207405SansPapyrus683Dreaming (IOI13_dreaming)C++20
18 / 100
49 ms19896 KiB
#include <bits/stdc++.h> #include "dreaming.h" #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)); } worst.push_back(farthest); baseline = max(baseline, farthest); } sort(worst.begin(), worst.end()); int w = worst.size(); if (w == 1) { return baseline; } else if (w == 2) { return worst[0] + l + worst[1]; } 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)); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...