| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1280995 | monval | 꿈 (IOI13_dreaming) | C++20 | 0 ms | 0 KiB |
#include "dreaming.h"
#include <vector>
#include <tuple>
#include <unordered_set>
#include <forward_list>
void swap(int &a, int &b){
int t = a;
a = b;
b = t;
}
int min(int a, int b){
if(a < b){
return a;
}else{
return b;
}
}
int max(int a, int b){
if(a < b){
return b;
}else{
return a;
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
int root_vertices[N - M];
unordered_set<int> child_edges[N];
int components[N];
for(int i = 0; i < N; i++){
components[i] = -1;
}
for(int i = 0; i < M; i++){
child_edges[A[i]].insert(i);
child_edges[B[i]].insert(i);
}
int eccentricities[N];
int current_component = 0;
int current_root = 0;
while(current_component < N - M){
if(components[current_root] != -1 || child_edges[current_root].size() > 1){
current_root++;
continue;
}
if(child_edges[current_root].empty()){
components[current_root] = current_component;
eccentricities[current_root] = 0;
current_root++;
current_component++;
continue;
}
root_vertices[current_component] = current_root;
forward_list<int> children = {current_root};
while(!children.empty()){
int child = children.front();
children.pop_front();
components[child] = current_component;
for(int edge : child_edges[child]){
if(A[edge] != child){
swap(A[edge], B[edge]);
}
child_edges[B[edge]].erase(edge);
children.push_front(B[edge]);
}
}
current_root++;
current_component++;
}
int heights[N];
int height_edges[N];
for(int i = 0; i < N; i++){
heights[i] = 0;
height_edges[i] = -1;
}
forward_list<tuple<int, bool> > height_calculation;
for(int i = 0; i < N - M; i++){
height_calculation.push_front(make_tuple(root_vertices[i], false));
}
while(!height_calculation.empty()){
int vertex;
bool status;
tie(vertex, status) = height_calculation.front();
height_calculation.pop_front();
if(status){
for(int edge : child_edges[vertex]){
int new_height = heights[B[edge]] + T[edge];
if(new_height > heights[vertex]){
heights[vertex] = new_height;
height_edges[vertex] = edge;
}
}
}else{
height_calculation.push_front(make_tuple(vertex, true));
for(int edge : child_edges[vertex]){
height_calculation.push_front(make_tuple(B[edge], false));
}
}
}
vector<int> max_paths[N - M];
for(int component = 0; component < N - M; component++){
int root = root_vertices[component];
max_paths[component] = {root};
while(true){
int last_vertex = max_paths[component].back();
if(height_edges[last_vertex] == -1){
break;
}
child_edges[last_vertex].erase(height_edges[last_vertex]);
max_paths[component].push_back(B[height_edges[last_vertex]]);
}
}
for(int component = 0; component < N - M; component++){
int best_upward[max_paths[component].size()];
best_upward[0] = 0;
for(int i = 1; i < max_paths[component].size(); i++){
best_upward[i] = best_upward[i - 1] + T[height_edges[max_paths[component][i - 1]]];
for(int edge : child_edges[max_paths[component][i]]){
int new_best = heights[B[edge]] + T[edge];
best_upward[i] = max(best_upward[i], new_best);
}
}
for(int i = 0; i < max_paths[component].size(); i++){
eccentricities[max_paths[component][i]] = max(heights[max_paths[component][i]], best_upward[i]);
}
}
forward_list<int> eccentricity_calculation;
for(vector<int> max_path : max_paths){
for(int vertex : max_path){
eccentricity_calculation.push_front(vertex);
}
}
while(!eccentricity_calculation.empty()){
int vertex = eccentricity_calculation.front();
eccentricity_calculation.pop_front();
for(int edge : child_edges[vertex]){
eccentricities[B[edge]] = eccentricities[vertex] + T[edge];
eccentricity_calculation.push_front(B[edge]);
}
}
int diameters[N - M];
int radii[N - M];
for(int i = 0; i < N - M; i++){
diameters[i] = 0;
radii[i] = eccentricities[root_vertices[i]];
}
for(int vertex = 0; vertex < N; vertex++){
diameters[components[vertex]] = max(diameters[components[vertex]], eccentricities[vertex]);
radii[components[vertex]] = min(radii[components[vertex]], eccentricities[vertex]);
}
int min_diameter = 0;
for(int i = 0; i < N - M; i++){
min_diameter = max(min_diameter, diameters[i]);
}
if(N - M == 1){
;
}else if(N - M == 2){
min_diameter = max(min_diameter, radii[0] + radii[1] + L);
}else{
int r1 = 0, r2 = 0, r3 = 0;
for(int i = 0; i < N - M; i++){
if(radii[i] >= r1){
r3 = r2;
r2 = r1;
r1 = radii[i];
}else if(radii[i] >= r2){
r3 = r2;
r2 = radii[i];
}else if(radii[i] >= r3){
r3 = radii[i];
}
}
min_diameter = max(min_diameter, r1 + r2 + L);
min_diameter = max(min_diameter, r2 + r3 + 2 * L);
}
return min_diameter;
}