제출 #1365847

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

race

#include "race.h"
#include <vector>
#include <map>
#include <functional>
using namespace std;
typedef pair<int,int> pi;
#define pb push_back

const int inf = 1e9;

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

    vector<long long> path(N);
    vector<int> dep(N);
    vector<vector<pi>> pres(N);
    int ans = inf;

    function<void(int,int,map<long long,int>&)> dfs = [&](int u, int p, map<long long,int>& mp) {
        mp[path[u]] = dep[u];
        pres[u].emplace_back((int)path[u], dep[u]);
        for (auto [v, w] : adj[u]) {
            if (v == p) continue;
            path[v] = path[u] + w;
            dep[v] = dep[u] + 1;
            map<long long,int> curr;
            dfs(v, u, curr);
            if (pres[u].size() < pres[v].size()) {
                swap(pres[u], pres[v]);
                swap(mp, curr);
            }
            for (auto [x, d] : pres[v]) {
                if (mp.find(2*path[u]+K-x) == mp.end()) continue;
                ans = min(ans, mp[2*path[u]+K-x] + d - 2*dep[u]);
            }
            for (auto [x, d] : pres[v]) {
                pres[u].emplace_back(x, d);
                if (mp.find(x) != mp.end()) mp[x] = min(mp[x], d);
                else mp[x] = d;
            }
        }
    };

    map<long long,int> tmp;
    dfs(0, -1, tmp);
    return ans == inf ? -1 : ans;
}

• 서브태스크 1: 9 / 9
• 서브태스크 2: 12 / 12
• 서브태스크 3: 22 / 22
• 서브태스크 4: 57 / 57