Submission #1131989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131989		hamidissocool	Race (IOI11_race)	C++20	100 / 100	357 ms	38708 KiB

race

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

using namespace std;

typedef pair<int, int> pii;

#define MAXN 200100
#define MAXK 1000100

#define F first
#define S second

int processed[MAXN], size[MAXN], achievable[MAXK], min_paths[MAXK];

vector<pii> neighbours[MAXN];

int bk, ga, split_node, current_max;

void calculate_size(int current, int parent){
    ::size[current] = 0;

    for (int i = 0; i < (int)neighbours[current].size(); i++){
        if (!processed[neighbours[current][i].F] && neighbours[current][i].F != parent){
            calculate_size(neighbours[current][i].F, current);
            ::size[current] += 1 + ::size[neighbours[current][i].F];
        }
    }
}


// we bout to get lit

void select_split_node(int current, int parent, int total){
    int n_max = total - ::size[current] - 1;
    for (int i = 0; i < (int)neighbours[current].size(); i++){
        if (!processed[neighbours[current][i].F] && neighbours[current][i].F != parent){
            select_split_node(neighbours[current][i].F, current, total);
            n_max = max(n_max, 1 + ::size[neighbours[current][i].F]);
        }
    }
    if (n_max < current_max){
        split_node = current;
        current_max = n_max;
    }
}

void dfs(int current, int parent, int current_cost, int current_length, int fill, int K){
    if (current_cost > K){
        return;
    }

    if (!fill){
        if (achievable[K - current_cost] == bk){
            if (current_length + min_paths[K - current_cost] < ga || ga == -1){
                ga = current_length + min_paths[K - current_cost];
            }
        }

        if (current_cost == K){
            if (current_length < ga || ga == -1){
                ga = current_length;
            }
        }
    }
    else {
        if (achievable[current_cost] < bk){
            achievable[current_cost] = bk;
            min_paths[current_cost] = current_length;
        }
        else if (current_length < min_paths[current_cost]){
            achievable[current_cost] = bk;
            min_paths[current_cost] = current_length;
        }
    }

    for (int i = 0; i < (int)neighbours[current].size(); i++){
        if (!processed[neighbours[current][i].F] && neighbours[current][i].F != parent){
            dfs(neighbours[current][i].F, current, current_cost + neighbours[current][i].S, current_length + 1, fill, K); // .S
        }
    }
}

// final steps

void process(int current, int K){
    calculate_size(current, -1);

    if (::size[current] <= 1){
        return;
    }

    split_node = -1;
    current_max = ::size[current] + 3;
    select_split_node(current, -1, ::size[current] + 1);

    bk++;

    for (int i = 0; i < (int)neighbours[split_node].size(); i++){
        if (!processed[neighbours[split_node][i].F]){
            dfs(neighbours[split_node][i].F, split_node, neighbours[split_node][i].S, 1, 0, K);
            dfs(neighbours[split_node][i].F, split_node, neighbours[split_node][i].S, 1, 1, K);
        }
    }

    int lsn = split_node;

    processed[split_node] = 1;

    for (int i = 0; i < (int)neighbours[lsn].size(); i++){
        if (!processed[neighbours[lsn][i].F]){
            process(neighbours[lsn][i].F, K);
        }
    }

}

// final steps


int best_path(int N, int K, int H[][2], int L[])
{
    memset(processed, 0, sizeof(processed));
    memset(achievable, 0, sizeof(achievable));
    memset(min_paths, 0, sizeof(min_paths));

    for (int i = 0; i < N - 1; i++){
        neighbours[H[i][0]].push_back({H[i][1], L[i]});
        neighbours[H[i][1]].push_back({H[i][0], L[i]}); // i believe??
    }
    ga = -1;
    process(0, K);
    return ga;
}

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