제출 #1283011

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283011		hubertm	경주 (Race) (IOI11_race)	C++20	100 / 100	275 ms	98888 KiB

race

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

using namespace std;

vector<pair<int, long long>> tree[200000];
int k;
set<pair<long long, int>> values[200000];
long long offsets[200000];
int edgeOffsets[200000];
int answer = 1e9;

void dfs(int node, int parent)
{
    if (tree[node].size() == 1 && node != 0) return;

    int chosen = -1;
    int chosenL = -1;
    for (auto [child, l] : tree[node])
    {
        if (child == parent) continue;

        dfs(child, node);
        if (chosen == -1 || values[child].size() > values[chosen].size())
        {
            chosen = child;
            chosenL = l;
        }
    }

    offsets[node] = offsets[chosen] + chosenL;
    edgeOffsets[node] = edgeOffsets[chosen] + 1;
    values[node].swap(values[chosen]);
    values[node].emplace(-offsets[node] + chosenL, -edgeOffsets[node] + 1);

    for (auto [child, l] : tree[node])
    {
        if (child == parent || child == chosen) continue;

        values[child].emplace(-offsets[child], -edgeOffsets[child]);

        for (auto [s, e] : values[child])
        {
            int v = k - (l + s + offsets[child] + offsets[node]);
            auto it = values[node].lower_bound(make_pair(v, INT_MIN));

            if (it != values[node].end() && it->first == v) answer = min(answer, it->second + e + 1 + edgeOffsets[child] + edgeOffsets[node]);
        }

        for (auto [s, e] : values[child])
        {
            int v = l + s + offsets[child] - offsets[node];
            values[node].emplace(v, e + edgeOffsets[child] - edgeOffsets[node] + 1);
        }
    }

    auto it = values[node].lower_bound(make_pair(k - offsets[node], INT_MIN));
    if (it != values[node].end() && it->first == k - offsets[node]) answer = min(answer, it->second + edgeOffsets[node]);
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;

    for (int i = 0; i < N - 1; ++i)
    {
        tree[H[i][0]].emplace_back(H[i][1], L[i]);
        tree[H[i][1]].emplace_back(H[i][0], L[i]);
    }

    if (N == 1) return -1;

    dfs(0, -1);

    if (answer == 1e9) return -1;
    else return answer;
}

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