| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1290408 | darekzhang | 꿈 (IOI13_dreaming) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
int travelTime(int N,int M,int L,
int A[],int B[],int T[]);
int subtree_dfs(int node, int N, vector<bool>& visited, vector<int>& subtree_depth, vector<vector<pair<int,int>>>& adj) {
if (visited[node]) return subtree_depth[node];
visited[node] = true;
int result = 0;
for (pair<int,int> child : adj[node]) {
if (!visited[child.first])
result = max(result,child.second + subtree_dfs(child.first,N,visited,subtree_depth,adj));
}
subtree_depth[node] = result;
// cout << "Subtree depth of " << node << ": " << result << "\n";
return result;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
set<int> roots {};
vector<int> root_of (N,-1);
vector<int> subtree_depth (N,0);
vector<int> parent (N,-1);
vector<vector<pair<int,int>>> adj (N, vector<pair<int,int>>{});
vector<bool> visited (N, false);
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]});
}
for (int i = 0; i < N; i++) {
if (root_of[i] != -1) continue;
// cout << "New root at: " << i << "\n";
roots.insert(i);
stack<int> dfs {};
dfs.push(i);
while (!dfs.empty()) {
int top = dfs.top();
dfs.pop();
root_of[top] = i;
for (pair<int,int> next : adj[top]) {
if (root_of[next.first] == -1) {
parent[next.first] = top;
dfs.push(next.first);
}
}
}
}
vector<int> min_tree_depths {};
min_tree_depths.reserve(roots.size());
for (int node : roots) {
// cout << "Tree with root: " << node << ": \n";
int result = INT_MAX;
subtree_dfs(node, N, visited, subtree_depth, adj);
pair<pair<int,int>,pair<int,int>> prev_largest_subtrees {{-1,0},{-1,0}};
pair<pair<int,int>,pair<int,int>> largest_subtrees {{-1,0},{-1,0}};
while (true) {
// cout << "Node: " << node << "\n";
largest_subtrees = {{-1,0},{-1,0}};
for (pair<int,int> next : adj[node]) {
int depth;
if (next.first == parent[node]) {
depth = prev_largest_subtrees.first.second + next.second;
} else {
depth = subtree_depth[next.first] + next.second;
}
// cout << "Depth of node: " << next.first << " is " << depth << "\n";
if (depth > largest_subtrees.second.second) {
largest_subtrees.first = largest_subtrees.second;
largest_subtrees.second = {next.first, depth};
} else if (depth > largest_subtrees.first.second) {
largest_subtrees.first = {next.first, depth};
}
}
prev_largest_subtrees = largest_subtrees;
result = min(result, largest_subtrees.second.second == -1 ? INT_MAX : largest_subtrees.second.second);
if (parent[node] == largest_subtrees.second.first)
break;
node = largest_subtrees.second.first;
}
min_tree_depths.push_back(result);
}
sort(min_tree_depths.begin(), min_tree_depths.end(), greater<int>{});
// for (int i : min_tree_depths)
// cout << i << " ";
// cout << "\n";
return min_tree_depths.size() == 2 ? min_tree_depths[0] + min_tree_depths[1] + L : max(min_tree_depths[0] + min_tree_depths[1] + L, min_tree_depths[1]+2*L+min_tree_depths[2]);
}
// int main() {
// int A[] = {0,8,2,5,5,1,1,10};
// int B[] = {8,2,7,11,1,3,9,6};
// int T[] = {4,2,4,3,7,1,5,3};
// return 0;
// }