Submission #1324790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1324790		pramad712	Dreaming (IOI13_dreaming)	C++17	100 / 100	141 ms	18660 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

int travelTime(int node_count, int edge_count, int added_weight, int firsts[], int seconds[], int weights[]) {
   vector<vector<pair<int, int>>> forest(node_count);

   for (int edge = 0; edge < edge_count; edge++) {
       forest[firsts[edge]].emplace_back(seconds[edge], weights[edge]);
       forest[seconds[edge]].emplace_back(firsts[edge], weights[edge]);
   }

   vector<pair<int, int>> centroids;

   vector<pair<int, int>> dp(node_count);
   vector<bool> visited(node_count);

   function<void(int, int)> inside_dfs = [&](int node, int parent) {
       for (auto [child, weight]: forest[node]) {
           if (child == parent) continue;

           inside_dfs(child, node);
           dp[node].first = max(dp[node].first, dp[child].first + weight);
       }
   };

   function<void(int, int)> outside_dfs = [&](int node, int parent) {
       pair<int, int> best = make_pair(dp[node].second, node), second_best = make_pair(0, 0);

       for (auto [child, weight]: forest[node]) {
           if (child == parent) continue;

           pair<int, int> distance = make_pair(dp[child].first + weight, child);

           if (distance > best) {
               second_best = best;
               best = distance;
           }

           else if (distance > second_best) {
               second_best = distance;
           }
       }

       for (auto [child, weight]: forest[node]) {
           if (child == parent) continue;

           if (best.second == child) {
               dp[child].second = second_best.first + weight;
           }

           else {
               dp[child].second = best.first + weight;
           }

           outside_dfs(child, node);
       }
   };

   for (int node = 0; node < node_count; node++) {
       if (visited[node]) continue;

       vector<int> tree;

       inside_dfs(node, -1);
       outside_dfs(node, -1);

       centroids.emplace_back(max(dp[node].first, dp[node].second), node);

       function<void(int, int)> centroid_dfs = [&](int node, int parent) {
           visited[node] = true;
           centroids.back() = min(centroids.back(), make_pair(max(dp[node].first, dp[node].second), node));

           for (auto [child, weight]: forest[node]) {
               if (child == parent) continue;
               centroid_dfs(child, node);
           }
       };

       centroid_dfs(node, -1);
   }

   sort(centroids.begin(), centroids.end());

   for (int index = 0; index < centroids.size() - 1; index++) {
       int first = centroids[index].second, second = centroids.back().second;
       forest[first].emplace_back(second, added_weight);
       forest[second].emplace_back(first, added_weight);
   }

   fill(dp.begin(), dp.end(), make_pair(0, 0));

   inside_dfs(centroids.back().second, -1);
   outside_dfs(centroids.back().second, -1);

   int diameter = 0;

   function<void(int, int)> diameter_dfs = [&](int node, int parent) {
       int best = dp[node].second, second_best = 0;

       for (auto [child, weight]: forest[node]) {
           if (child == parent) continue;

           int distance = dp[child].first + weight;

           if (distance > best) {
               second_best = best;
               best = distance;
           }

           else if (distance > second_best) {
               second_best = distance;
           }

           diameter_dfs(child, node);
       }

       diameter = max(diameter, best + second_best);
   };

   diameter_dfs(centroids.back().second, -1);

   return diameter;
}

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