제출 #1213973

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213973		tuankhang13	Race (IOI11_race)	C++20	100 / 100	624 ms	38796 KiB

race

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
using namespace std;

const int maxn = 2e5 + 13;
int n, k, res;
vector<pii> adj[maxn];
vector<int> del(maxn, 0), child(maxn);
map<int, int> mp;

void dfs(int u, int p) {
    child[u] = 1;
    for (auto x : adj[u]) {
        int v = x.fi;
        if (v != p && !del[v]) {
            dfs(v, u);
            child[u] += child[v];
        }
    }
}

int find_ctroid(int u, int p, int sz) {
    for (auto x : adj[u]) {
        int v = x.fi;
        if (v != p && !del[v] && child[v] > sz / 2) {
            return find_ctroid(v, u, sz);
        }
    }
    return u;
}

void cointect(int u, int p, int depth, int dist, bool fil) {
    if (dist > k) return;
    if (fil) {
        if (mp.find(dist) != mp.end()) {
            mp[dist] = min(mp[dist], depth);
        } else {
            mp[dist] = depth;
        }
    } else {
        if (mp.find(k - dist) != mp.end()) {
            res = min(res, depth + mp[k - dist]);
        }
    }
    for (auto x : adj[u]) {
        int v = x.fi;
        if (v != p && !del[v]) {
            cointect(v, u, depth + 1, dist + x.se, fil);
        }
    }
}

void decompose(int u) {
    dfs(u, 0);
    int ct = find_ctroid(u, 0, child[u]);
    del[ct] = 1;

    mp.clear();
    mp[0] = 0;

    for (auto x : adj[ct]) {
        int v = x.fi;
        if (!del[v]) {
            cointect(v, ct, 1, x.se, 0);  
            cointect(v, ct, 1, x.se, 1);  
        }
    }

    for (auto x : adj[ct]) {
        int v = x.fi;
        if (!del[v]) {
            decompose(v);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N;
    k = K;

    for (int i = 0; i < n - 1; ++i) {
        int u = H[i][0], v = H[i][1], w = L[i];
        ++u, ++v;  
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }

    res = INT_MAX;
    decompose(1);  

    return (res == INT_MAX ? -1 : res);
}

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