제출 #1228438

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228438		Muhammet	Race (IOI11_race)	C++20	9 / 100	69 ms	25668 KiB

race

#include "bits/stdc++.h"
#include "race.h"
// #include "grader.cpp"

using namespace std;

#define ll long long

vector <vector <pair <int, int>>> v;

vector <ll> dep, depth, s;

ll ans, KKK;

vector <map <ll, ll>> mp;

void dfs(int x, int y) {
    s[x] = 1;
    for(auto [i, j] : v[x]) {
        if(i == y) continue;
        dep[i] = dep[x] + j;
        depth[i] = depth[x] + 1;
        dfs(i, x);
        s[x] += s[i];
    }
}

void f(int x, int y) {
    int mx = -1, hv = -1;
    for(auto [i, j] : v[x]) {
        if(i == y) continue;
        f(i, x);
        if(s[i] > mx) {
            hv = i;
            mx = s[i];
        }
    }
    if(~hv) swap(mp[x], mp[hv]);
    for(auto [i, j] : v[x]) {
        if(i == hv or i == y) continue;
        for(auto [k, nm] : mp[i]) {
            if(mp[x].find(KKK - k) == mp[x].end()) continue;
            ans = min(ans, mp[x][k - KKK] + nm - 2 * depth[x] + 1);
        }
        for(auto [k, nm] : mp[i]) {
            if(mp[x].find(k) == mp[x].end()) mp[x][k] = nm;
            else mp[x][k] = min(nm, mp[x][k]);
        }
    }
    if(mp[x].find(dep[x] + KKK) != mp[x].end()) ans = min(ans, mp[x][dep[x] + KKK] - depth[x]);
    mp[x][dep[x]] = depth[x];
}


int best_path(int n, int KK, int h[][2], int l[]) {
    KKK = KK;
    v.resize(n+1);
    mp.resize(n+1);
    dep.resize(n+1);
    depth.resize(n+1);
    s.resize(n+1);
    dep[0] = depth[0] = 0;
    for(int i = 0; i < n-1; i++) {
        v[h[i][0]].push_back({h[i][1], l[i]});
        v[h[i][1]].push_back({h[i][0], l[i]});
    }
    ans = 1e9;
    dfs(0, -1);
    f(0, -1);
    return (ans == 1e9 ? -1 : ans);
}

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