제출 #1210782

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210782		Born_To_Laugh	Race (IOI11_race)	C++17	21 / 100	3095 ms	11516 KiB

race

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<60);

int N, K;
vector<vector<pair<int,int>>> adj;
vector<ll> sumv;     // sum of weights from root to u
vector<int> depthv;  // depth (number of edges) from root to u
vector<int> sz, heavy;
ll answer = INF;

// for DSU on tree
unordered_map<ll,int> mp;  
int curRoot;

// 1) dfs1: tính sumv[], depthv[], sz[] và xác định heavy[u]
void dfs1(int u, int p){
    sz[u] = 1;
    heavy[u] = -1;
    for (auto &[v,w] : adj[u]) if (v != p){
        sumv[v]   = sumv[u] + w;
        depthv[v] = depthv[u] + 1;
        dfs1(v, u);
        if (heavy[u] == -1 || sz[v] > sz[ heavy[u] ])
            heavy[u] = v;
        sz[u] += sz[v];
    }
}

// helper: cập nhật answer khi gặp node x với gốc curRoot
inline void query_node(int x){
    ll need = (ll)K + 2*sumv[curRoot] - sumv[x];
    auto it = mp.find(need);
    if (it != mp.end())
        answer = min(answer, (ll)depthv[x] + it->second - 2LL*depthv[curRoot]);
}

// helper: thêm node x vào mp (lưu depth nhỏ nhất)
inline void add_node(int x){
    auto it = mp.find(sumv[x]);
    if (it == mp.end())        mp[ sumv[x] ] = depthv[x];
    else                        it->second = min(it->second, depthv[x]);
}

// traverse subtree of u:
//   if doQuery==true: query each node x against current mp
//   else             : insert each node x into mp
void dfs_add(int u, int p, bool doQuery){
    if (doQuery)  query_node(u);
    else          add_node(u);

    for (auto &[v,w] : adj[u]) if (v != p){
        dfs_add(v, u, doQuery);
    }
}

// 2) dfs2: DSU on tree chính
void dfs2(int u, int p, bool keep){
    // 1) xử lý tất cả con nhỏ trước (clear xong)
    for (auto &[v,w] : adj[u]) if (v != p && v != heavy[u])
        dfs2(v, u, false);

    // 2) xử lý con heavy, giữ lại mp
    if (heavy[u] != -1)
        dfs2(heavy[u], u, true);

    // 3) merge các light subtrees vào mp, trước tiên query thỏa mãn, rồi insert
    for (auto &[v,w] : adj[u]) if (v != p && v != heavy[u]){
        curRoot = u;
        dfs_add(v, u, true);   // query mọi node trong subtree v
        dfs_add(v, u, false);  // rồi add tất cả vào mp
    }

    // 4) cuối cùng xử lý chính u
    curRoot = u;
    query_node(u);
    add_node(u);

    // 5) nếu không giữ thì clear hết
    if (!keep) 
        mp.clear();
}

int best_path(int n, int k, int edges[][2], int weights[]){
    N = n;  K = k;
    adj.assign(N, {});
    sumv.assign(N, 0);
    depthv.assign(N, 0);
    sz.assign(N, 0);
    heavy.assign(N, -1);
    answer = INF;
    mp.reserve(N*2);

    // build graph
    for (int i = 0; i < N-1; i++){
        int u = edges[i][0], v = edges[i][1];
        int w = weights[i];
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    // 1) precompute sizes, heavy, sums, depths
    dfs1(0, -1);
    // 2) dsu on tree
    dfs2(0, -1, false);
    return (answer == INF ? -1 : (int)answer);
}

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