제출 #1214554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1214554		ericl23302	Race (IOI11_race)	C++20	43 / 100	3095 ms	83944 KiB

race

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

using namespace std;

void recurse(int N, int K, vector<vector<pair<int, int>>> &adjacency, vector<map<int, int>> &maps, int &res, int cur, int parent) {
    maps[cur][0] = 0;
    for (auto &[child, length] : adjacency[cur]) {
        if (child == parent) continue;
        recurse(N, K, adjacency, maps, res, child, cur);
        for (auto i = prev(maps[child].end()); ; ) {
            auto &[a, b] = *i; 
            bool bre = true;
            if (i != maps[child].begin()) bre = false, --i;
            maps[child].erase(a);
            if (a + length <= K) maps[child][a + length] = b + 1;
            if (bre) break;
        }

        if (maps[cur].size() < maps[child].size()) swap(maps[cur], maps[child]);
        maps[cur][0] = maps[child][0] = 0;
        for (auto &[i, j] : maps[child]) {
            if (maps[cur].count(K - i)) res = min(res, j + maps[cur][K - i]);
        }

        for (auto &[i, j] : maps[child]) {
            if (maps[cur].count(i)) maps[cur][i] = min(maps[cur][i], j);
            else maps[cur][i] = j;
        }
    }
}

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

    vector<map<int, int>> maps(N);
    int res = 1e9;
    recurse(N, K, adjacency, maps, res, 0, -1);

    return (res < 1e9 ? res : -1);
}

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