제출 #717809

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
717809		Charizard2021	경주 (Race) (IOI11_race)	C++17	100 / 100	651 ms	41720 KiB

race

#include<bits/stdc++.h>
using namespace std;
const int N = 200001;
const int K = 1000001;
int n, k, global_answer;
int split_node, current_max;
int book_keeping;
int H[N][2];
int L[N];
int processed[N];
int size2[N];
int achievable[K];
int minimum_paths[K];
vector<pair<int, int> > adj[N];
void calc_size(int current, int parent){
    size2[current] = 0;
    int i;
    for (i = 0; i < (int)adj[current].size(); i++){
        if (!processed[adj[current][i].first] && adj[current][i].first != parent){
            calc_size(adj[current][i].first, current);
            size2[current] += 1 + size2[adj[current][i].first];
        }
    }
}
void select_split_node(int current, int parent, int total){
    int node_max = (total - size2[current] - 1);
    int i;
    for (i = 0; i < (int)adj[current].size(); i++){
        if (!processed[adj[current][i].first] && adj[current][i].first != parent){
            select_split_node(adj[current][i].first, current, total);
            node_max = max(node_max, 1 + size2[adj[current][i].first]);
        }
    }
    if (node_max < current_max)
    {
        split_node = current;
        current_max = node_max;
    }
}
void dfs_from_node(int current, int parent, int current_cost, int current_length, int fill){
    if (current_cost > k)
        return;

    if (!fill){
        if (achievable[k - current_cost] == book_keeping){
            if (current_length + minimum_paths[k - current_cost] < global_answer || global_answer == -1){
                global_answer = current_length + minimum_paths[k - current_cost];
            }
        }

        if (current_cost == k){
            if (current_length < global_answer || global_answer == -1){
                global_answer = current_length;
            }
        }
    }
    else{
        if (achievable[current_cost] < book_keeping)
        {
            achievable[current_cost] = book_keeping;
            minimum_paths[current_cost] = current_length;
        }
        else if (current_length < minimum_paths[current_cost])
        {
            achievable[current_cost] = book_keeping;
            minimum_paths[current_cost] = current_length;
        }
    }
    int i;
    for (i = 0; i < (int)adj[current].size(); i++){
        if (!processed[adj[current][i].first] && adj[current][i].first != parent){
            dfs_from_node(adj[current][i].first, current, current_cost + adj[current][i].second, current_length + 1, fill);
        }
    }
}
void process(int current){
    calc_size(current, -1);
    if (size2[current] <= 1){
        return;
    }
    split_node = -1;
    current_max = size2[current] + 3;
    select_split_node(current, -1, size2[current] + 1);
    book_keeping++;
    int i;
    for (i = 0; i < (int)adj[split_node].size(); i++){
        if (!processed[adj[split_node][i].first]){
            dfs_from_node(adj[split_node][i].first, split_node, adj[split_node][i].second, 1, 0);
            dfs_from_node(adj[split_node][i].first, split_node, adj[split_node][i].second, 1, 1);
        }
    }
    int local_split_node = split_node;
    processed[split_node] = 1;
    for (i = 0; i < (int)adj[local_split_node].size(); i++){
        if (!processed[adj[local_split_node][i].first]){
            process(adj[local_split_node][i].first);
        }
    }
}
int best_path(int _N, int _K, int H[][2], int L[]){
    memset(processed, 0, sizeof processed);
    memset(achievable, 0, sizeof achievable);
    memset(minimum_paths, 0, sizeof minimum_paths);
    n = _N;
    k = _K;
    book_keeping = 0;
    int i;
    for (i = 0; i < n - 1; i++){
        adj[H[i][0]].push_back(make_pair(H[i][1], L[i]));
        adj[H[i][1]].push_back(make_pair(H[i][0], L[i]));
    }

    global_answer = -1;
    process(0);

    return global_answer;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57