제출 #1290409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290409		darekzhang	Dreaming (IOI13_dreaming)	C++20	0 / 100	33 ms	13072 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;

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;
// }

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