Submission #881997

#	Time	Username	Problem	Language	Result	Execution time	Memory
881997		chanhchuong123	Race (IOI11_race)	C++17	100 / 100	324 ms	38296 KiB

race

#include <bits/stdc++.h>
#include <race.h>
using namespace std;
#define task ""
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

const int INF = 1e9 + 7;
const int MAX = 200020;
int n, k;
vector<pair<int, int>> adj[MAX];

int sz[MAX];
bool rem[MAX];

int dfsSZ(int u, int p) {
    sz[u] = 1;
    for (auto [v, w]: adj[u]) if (v != p && !rem[v]) {
        sz[u] += dfsSZ(v, u);
    }
    return sz[u];
}

int findCentroid(int u, int p, int n) {
    for (auto [v, w]: adj[u]) if (v != p && !rem[v]) {
        if (2 * sz[v] > n)
            return findCentroid(v, u, n);
    }
    return u;
}

int h[MAX];
int dep[MAX];
int res = +INF;
int maxHigh[1000010];

void dfs(int u, int p, bool upd) {
    if (dep[u] > k) return;
    if (!upd) res = min(res, h[u] + maxHigh[k - dep[u]]);
    if (upd) maxHigh[dep[u]] = min(maxHigh[dep[u]], h[u]);
    for (auto [v, w]: adj[u]) if (v != p && !rem[v]) {
        dep[v] = dep[u] + w;
        h[v] = h[u] + 1;
        dfs(v, u, upd);
    }
}

void del(int u, int p) {
    if (dep[u] > k) return;
    maxHigh[dep[u]] = +INF;
    for (auto [v, w]: adj[u]) if (v != p && !rem[v]) del(v, u);
}

void solve(int u, int p) {
    int c = findCentroid(u, p, dfsSZ(u, p)); rem[c] = true;

    dep[c] = h[c] = 0;
    for (auto [v, w]: adj[c]) if (v != p && !rem[v]) {
        dep[v] = dep[c] + w;
        h[v] = h[c] + 1;
        dfs(v, c, 0);
        dfs(v, c, 1);
    }
    for (auto [v, w]: adj[c]) if (v != p && !rem[v]) {
        del(v, c);
    }

    for (auto [v, w]: adj[c]) if (v != p && !rem[v]) {
        solve(v, c);
    }
}

int best_path(int _n, int _k, int H[][2], int L[]) {
	n = _n; k = _k;
    for (int i = 0; i <= k; ++i) {
        maxHigh[i] = +INF;
    }
	for (int i = 0; i < n - 1; i++) {
		int u = H[i][0], v = H[i][1], l = L[i];
		adj[u].emplace_back(v, l);
        adj[v].emplace_back(u, l);
	}
	maxHigh[0] = 0; solve(0, -1);
  	return (res == +INF ? -1 : res);
}

//int main() {
//	ios_base::sync_with_stdio(false); cin.tie(nullptr);
//
//	if (fopen(task".inp", "r")) {
//		freopen(task".inp", "r",  stdin);
//		freopen(task".out", "w", stdout);
//	}
//
//    cin >> n >> k;
//    for (int i = 0; i <= k; ++i) {
//        maxHigh[i] = +INF;
//    }
//    for (int i = 1; i < n; ++i) {
//        int u, v, l; cin >> u >> v >> l;
//        adj[u].emplace_back(v, l);
//        adj[v].emplace_back(u, l);
//    }
//    maxHigh[0] = 0; solve(0, -1);
//    cout << (res == INF ? -1 : res);
//	return 0;
//}

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