Submission #1059059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059059		CodeLakVN	Race (IOI11_race)	C++17	100 / 100	195 ms	41428 KiB

race

#ifndef LAK
#include <race.h>
#endif // LAK

#include <bits/stdc++.h>

#define no "NO"
#define yes "YES"
#define F first
#define S second
#define vec vector
#define task "main"
#define ll long long
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maximize(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool minimize(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)2e5 + 9;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;

int numNode, numDist;
vector<ii> adj[N];
int child[N], minEdge[(int)1e6 + 5];
bool del[N];
int ans = INF;

int countChild(int u, int p) {
    child[u] = 1;
    for (auto [v, w] : adj[u]) {
        if (v == p || del[v]) continue;
        countChild(v, u);
        child[u] += child[v];
    }
    return child[u];
}

int centroid(int u, int p, int m) {
    for (auto [v, w] : adj[u]) {
        if (v == p || del[v]) continue;
        if (child[v] > m / 2) return centroid(v, u, m);
    }
    return u;
}

void DFS_calc(int u, int p, int depth, int curLen) {
    if (curLen > numDist) return;
    minimize(ans, depth + minEdge[numDist - curLen]);
    for (auto [v, w] : adj[u]) {
        if (del[v] || v == p) continue;
        DFS_calc(v, u, depth + 1, curLen + w);
    }
}

void DFS_minimize(int u, int p, int depth, int curLen, vector<int> &tmp) {
    if (curLen > numDist) return;
    tmp.push_back(curLen);
    minimize(minEdge[curLen], depth);
    for (auto [v, w] : adj[u]) {
        if (del[v] || v == p) continue;
        DFS_minimize(v, u, depth + 1, curLen + w, tmp);
    }
}

void cd(int u) {
    int m = countChild(u, 0);
    u = centroid(u, 0, m);

    vector<int> tmp;
    for (auto [v, w] : adj[u]) {
        if (del[v]) continue;
        DFS_calc(v, u, 1, w);
        DFS_minimize(v, u, 1, w, tmp);
    }
    del[u] = 1;

    for (int len : tmp) minEdge[len] = INF;

    for (auto [v, w] : adj[u]) {
        if (del[v]) continue;
        cd(v);
    }
}

int best_path(int n, int k, int h[][2], int l[]) {
    numNode = n;
    numDist = k;
    FOR(i, 0, numNode - 2) {
        int u = h[i][0], v = h[i][1];
        int w = l[i];
        u++;
        v++;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    FOR(i, 1, (int)1e6) minEdge[i] = INF;

    cd(1);

    return (ans != INF ? ans : -1);
}

#ifdef LAK
int edge[N][2];
int length[N];

void main_code() {
    int numNode, requireDist;
    cin >> numNode >> requireDist;
    FOR(i, 0, numNode - 2) {
        int u, v, l;
        cin >> u >> v >> l;
        edge[i][0] = u, edge[i][1] = v;
        length[i] = l;
    }
    cout << best_path(numNode, requireDist, edge, length);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    const bool MULTITEST = 0;
    int num_test = 1; if (MULTITEST) cin >> num_test;
    while (num_test--) { main_code(); cout << "\n"; }
}
#endif // LAK

/* Lak lu theo dieu nhac */

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