제출 #724437

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
724437		adrilen	Race (IOI11_race)	C++17	0 / 100	11 ms	19112 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;

constexpr int maxn = 2e5;
int n, k;


basic_string <int> city[maxn]; 
basic_string <int> adj[maxn][2]; // One for each side of the edge

int siz[maxn][2] = { 0 };
bool removed[maxn] = { 0 };

int find_side(int p, int par)
{
    auto it = lower_bound(adj[p][0].begin(), adj[p][0].end(), par);
    return ((it == adj[p][0].end() || *it != par) + 1 ) & 1;
}


int calc_size(int p, int par, int subtree)
{
    // Start
    if (par == -1)
    {
        siz[p][0] = 0;
        for (int i : adj[p][0])
        {
            if (removed[i]) continue;
            siz[p][0] += calc_size(i, p, subtree) + 1;
        }
        siz[p][1] = 0;
        for (int i : adj[p][1])
        {
            if (removed[i]) continue;
            siz[p][1] += calc_size(i, p, subtree) + 1;

        }
        return 0;
    }

    int side = find_side(p, par);

    siz[p][side] = 0;

    for (int i : adj[p][side])
    {
        if (i == par) abort();
        if (removed[i]) continue;
        siz[p][side] += calc_size(i, p, subtree) + 1;
    }
    siz[p][(side + 1) & 1] = subtree - 1 - siz[p][side];
    return siz[p][side];
}

int find_centroid(int p)
{
    if (abs(siz[p][0] - siz[p][1]) <= 1) return p;

    int side = (siz[p][0] < siz[p][1]);

    for (int i : adj[p][side])
    {
        if (removed[i]) continue;
        if (abs(siz[p][0] - siz[p][1]) <= abs(siz[i][0] - siz[i][1])) continue;
        return find_centroid(i);
    }
    return p;
}


vector <pii> scores[2];

void dfs(int p, int par, int val, int &max_val, int *l, int &side, int length)
{
    length++;
    val += l[p];
    if (val > max_val) return ;
    scores[side].emplace_back(pii(val, length));

    if (par == -1)
    {
        for (int i : adj[p][0])
        {
            if (removed[i]) continue;
            dfs(i, p, val, max_val, l, side, length);
        }
        for (int i : adj[p][1])
        {
            if (removed[i]) continue;
            dfs(i, p, val, max_val, l, side, length);
        }
        return ;
    }

    int s = find_side(p, par);
    for (int i : adj[p][s])
    {
        if (removed[i]) continue;
        dfs(i, p, val, max_val, l, side, length);
    }
}

int output = 1e9;

void centroid_decomp(int centroid, int subtree, int *l)
{
    // cout << centroid << endl;
    removed[centroid] = true;

    // Calculate
    scores[0].clear();
    scores[1].clear();

    int nk = k - l[centroid];

    scores[0].emplace_back(pii(0, 0)); 
    scores[1].emplace_back(pii(0, 0));

    for (int s = 0; s <= 1; s++) {
        for (int i : adj[centroid][s])
        {
            if (removed[i]) continue;
            dfs(i, -1, 0, nk, l, s, 0);
        }
    }


    sort(scores[0].begin(), scores[0].end());
    sort(scores[1].begin(), scores[1].end());

    auto it = scores[0].begin();
    auto rt = scores[1].rbegin();
    // for (pii p : scores[0]) cout << p.first << " " << p.second << "\n";

    while (it != scores[0].end() && rt != scores[1].rend())
    {
        if ((*it).first + (*rt).first == nk)
        {
            output = min(output, (*it).second + (*rt).second + 1);
            // cerr << centroid << " " << output << " " << (*it).first << " " << (*rt).first << " " << l[centroid] << " " << nk << " ";
            // cerr << (*it).second << " " << (*rt).second << "\n";
            it++;
        } else if ((*it).first + (*rt).first < nk) it++;
        else rt++; 
    }

    // Left
    for (int i : adj[centroid][0])
    {
        if (removed[i]) continue;
        calc_size(i, -1, siz[centroid][0]);
        centroid_decomp(find_centroid(i), siz[centroid][0], l);
        break;
    }

    // Right
    for (int i : adj[centroid][1])
    {
        if (removed[i]) continue;
        calc_size(i, -1, siz[centroid][1]);
        centroid_decomp(find_centroid(i), siz[centroid][1], l);
        break;
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    // cout << "start" << endl;
    n = N - 1, k = K;

    for (int i = 0; i < n; i++)
    {
        city[H[i][0]].push_back(i);
        city[H[i][1]].push_back(i);
    }

    for (int i = 0; i < n; i++)
    {
        for (int y : city[H[i][0]]) 
        {
            if (y == i) continue;
            adj[i][0].push_back(y);
        }
        for (int y : city[H[i][1]]) 
        {
            if (y == i) continue;
            adj[i][1].push_back(y);
        }
        if (adj[i][0].size() > adj[i][1].size()) swap(adj[i][0], adj[i][1]);    // Potentially very slow
        sort(adj[i][0].begin(), adj[i][0].end());
        
        // sort(adj[i][1].begin(), adj[i][1].end());
    }
    // cout << "start2" << endl;
    int p = 0;
    calc_size(p, -1, n);
    // cout << "start3" << endl;


    centroid_decomp(find_centroid(p), n, L);
    
    // cerr << clock() / static_cast<double>(CLOCKS_PER_SEC) << "\n";
    return (output == 1e9 ? -1 : output);
}

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