제출 #1280999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280999		monval	Dreaming (IOI13_dreaming)	C++20	100 / 100	273 ms	27136 KiB

dreaming

#include "dreaming.h"

#include <vector>
#include <tuple>
#include <unordered_set>
#include <forward_list>

using namespace std;

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;
        }
        root_vertices[current_component] = current_root;
        if(child_edges[current_root].empty()){
            components[current_root] = current_component;
            eccentricities[current_root] = 0;
            current_root++;
            current_component++;
            continue;
        }
        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;
}

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