제출 #680367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
680367		pls33	경주 (Race) (IOI11_race)	C++17	9 / 100	3071 ms	32536 KiB

race

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#ifndef _AAAAAAAAA
#include "race.h"
#endif

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
#pragma endregion

using state_t = bitset<(int)2e5>;

using map_t = gp_hash_table<int, int>;

void merge_maps(map_t &path, map_t &new_path)
{
    if (path.size() < new_path.size())
    {
        new_path.swap(path);
    }

    for (auto &[sum, len] : new_path)
    {
        auto it = path.find(sum);

        if (it == path.end())
        {
            path[sum] = len;
        }
        else
        {
            it->second = min(it->second, len);
        }
    }
}

void find_size(int v, int p,
               vi32 &size, vvp32 &adj, state_t &deleted)
{
    if (deleted[v])
    {
        size[v] = 0;
        return;
    }

    size[v] = 1;
    for (auto &[next, len] : adj[v])
    {
        if (next == p || deleted[v])
        {
            continue;
        }

        find_size(next, v, size, adj, deleted);
        size[v] += size[next];
    }
}

void find_centroid(int v, int p, int needed,
                   int &centroid,
                   vi32 &size, vvp32 &adj, state_t &deleted)
{
    if (deleted[v])
    {
        return;
    }

    bool ok = true;
    for (auto &[next, len] : adj[v])
    {
        if (size[next] <= needed || next == p || deleted[next])
        {
            continue;
        }

        find_centroid(next, v, needed, centroid, size, adj, deleted);
        ok = false;
        break;
    }

    if (centroid == -1 && ok)
    {
        centroid = v;
    }
}

int update_length(int sum, int length, map_t &map)
{
    auto it = map.find(sum);

    if (it == map.end())
    {
        map[sum] = length;
        return length;
    }

    it->second = min(it->second, length);
    return it->second;
}

void find_paths(int v, int p, int sum, int length, int K,
                int &shortest,
                map_t &path, map_t &new_path, vvp32 &adj, state_t &deleted)
{
    if (sum > K || deleted[v])
    {
        return;
    }

    if (sum == K)
    {
        shortest = min(shortest, length);
        return;
    }

    int cur_length = update_length(sum, length, new_path);
    auto it = path.find(K - sum);

    if (it != path.end())
    {
        shortest = min(shortest, it->second + cur_length);
    }

    for (auto &[next, len] : adj[v])
    {
        if (next == p || deleted[next])
        {
            continue;
        }

        find_paths(next, v, sum + len, length + 1, K,
                   shortest,
                   path, new_path, adj, deleted);
    }
}

void eval_centroid(int v, int K,
                   int &shortest,
                   map_t &path, map_t &new_path,
                   vi32 &size, vvp32 &adj, state_t &deleted)
{
    find_size(v, -1, size, adj, deleted);
    if (size[v] < 2)
    {
        return;
    }

    int centroid = -1;
    find_centroid(v, -1, size[v] / 2, centroid, size, adj, deleted);

    deleted[centroid] = true;
    for (auto &[next, len] : adj[centroid])
    {
        if (deleted[next])
        {
            continue;
        }

        find_paths(next, -1, len, 1, K, shortest, path, new_path, adj, deleted);
        merge_maps(path, new_path);
        new_path.clear();
    }
    path.clear();

    for (auto &[next, len] : adj[centroid])
    {
        if (deleted[next])
        {
            continue;
        }
        eval_centroid(next, K, shortest, path, new_path, size, adj, deleted);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    vvp32 adj(N);
    for (int i = 0; i < N - 1; i++)
    {
        adj[H[i][0]].emplace_back(H[i][1], L[i]);
        adj[H[i][1]].emplace_back(H[i][0], L[i]);
    }

    int shortest = N + 1;
    vi32 size(N);
    state_t deleted;
    map_t path({}, {}, {}, {}, {1 << 20}), new_path({}, {}, {}, {}, {1 << 20});

    eval_centroid(0, K, shortest, path, new_path, size, adj, deleted);

    return shortest == N + 1 ? -1 : shortest;
}

#ifdef _AAAAAAAAA
#define MAX_N 500000
static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];

void read_input()
{
    int i;
    scanf("%d %d", &N, &K);
    for (i = 0; i < N - 1; i++)
        scanf("%d %d %d", &H[i][0], &H[i][1], &L[i]);
}

int main()
{
    freopen("race.in", "r", stdin);
    int ans;
    read_input();
    ans = best_path(N, K, H, L);
    printf("%d\n", ans);
    return 0;
}
#endif

컴파일 시 표준 에러 (stderr) 메시지

race.cpp:12: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
   12 | #pragma region dalykai
      | 
race.cpp:35: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   35 | #pragma endregion
      |

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