제출 #1210858

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210858		Born_To_Laugh	경주 (Race) (IOI11_race)	C++17	100 / 100	595 ms	69292 KiB

race

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;

int n, k;
int ans;
vector<int> dep, distv, sz, bigchild;
vector<vector<int>> adj;
unordered_map<int,int> mp;
unordered_map<long long,int> wei;

void pre_dfs(int u, int p){
    sz[u] = 1;
    for(int v : adj[u]) if (v != p) {
        dep[v] = dep[u] + 1;
        distv[v] = distv[u] + wei[( (ll)u<<32 ) | v];
        pre_dfs(v, u);
        sz[u] += sz[v];
        if (bigchild[u] < 0 || sz[v] > sz[ bigchild[u] ])
            bigchild[u] = v;
    }
}

void calc_down(int u, int p, int distlca, int deplca){
    int want = k + 2*distlca - distv[u];
    auto it = mp.find(want);
    if (it != mp.end())
        ans = min(ans, it->second + dep[u] - 2*deplca);
    for(int v : adj[u]) if (v != p)
        calc_down(v, u, distlca, deplca);
}

void add_down(int u, int p){
    auto it = mp.find(distv[u]);
    if (it == mp.end()) mp[distv[u]] = dep[u];
    else it->second = min(it->second, dep[u]);
    for(int v : adj[u]) if (v != p)
        add_down(v, u);
}

void dfs(int u, int p, bool keep){
    // xử lý các nhánh nhỏ trước
    for(int v : adj[u]) if (v!=p && v!=bigchild[u])
        dfs(v, u, false);
    // rồi đến nhánh lớn
    if (bigchild[u] >= 0)
        dfs(bigchild[u], u, true);
    // xử lý các nhánh nhỏ: kiểm tra + thêm vào map
    for(int v : adj[u]) if (v!=p && v!=bigchild[u]) {
        calc_down(v, u, distv[u], dep[u]);
        add_down(v, u);
    }
    // cuối cùng tự xử lý u
    // trước hết kiểm pair case chỉ 1 node
    int want0 = k + distv[u];
    auto it0 = mp.find(want0);
    if (it0 != mp.end())
        ans = min(ans, it0->second - dep[u]);
    // sau đó thêm u
    auto it1 = mp.find(distv[u]);
    if (it1 == mp.end()) mp[distv[u]] = dep[u];
    else it1->second = min(it1->second, dep[u]);

    if (!keep) {
        mp.clear();
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    n = N; k = K;
    adj.assign(n, {});
    dep.assign(n,0); distv.assign(n,0);
    sz.assign(n,0); bigchild.assign(n,-1);
    // build
    for(int i=0;i<n-1;i++){
        int x=H[i][0], y=H[i][1];
        adj[x].push_back(y);
        adj[y].push_back(x);
        wei[( (ll)x<<32 )|y] = L[i];
        wei[( (ll)y<<32 )|x] = L[i];
    }
    ans = INF;
    pre_dfs(0,-1);

    // khởi tạo map với root
    mp.clear();
    mp[0] = 0;  // dist[0]=0, dep[0]=0

    dfs(0, -1, false);
    return ans==INF? -1 : ans;
}

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