Submission #717807

#	Time	Username	Problem	Language	Result	Execution time	Memory
717807		Charizard2021	Race (IOI11_race)	C++17	9 / 100	181 ms	88232 KiB

race

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N, K;

set<ll> adj[200001];
map<ll, ll> costs[200001];
ll subtree[200001], first_centroid;

ll A[1000001], component = 0, ans = 200001;
ll achievable[1000001], min_paths[1000001];
void get_subtree_sizes(ll node, ll parent) {
    subtree[node] = 1;
    for (ll i : adj[node])
        if (i != parent) {
            get_subtree_sizes(i, node);
            subtree[node] += subtree[i];
        }
}
ll get_centroid(ll node, ll parent, ll tree_size) {
    for (ll i : adj[node])
        if (i != parent && subtree[i] > tree_size)
            return get_centroid(i, node, tree_size);
    return node;
}
void dfs(ll node, ll parent, ll cost, ll depth, bool filling) {
    if (cost > K) return;

    if (filling) {
        if (achievable[K - cost] == component)
            ans = min(ans, depth + min_paths[K - cost]);
        if (cost == K) ans = min(ans, depth);
    } else {
        if (achievable[cost] < component || depth < min_paths[cost]) {
            achievable[cost] = component;
            min_paths[cost] = depth;
        }
    }

    for (ll i : adj[node])
        if (i != parent)
            dfs(i, node, cost + costs[node][i], depth + 1, filling);
}
void process(ll node) {
    get_subtree_sizes(node, 0);
    ll centroid = get_centroid(node, 0, subtree[node] / 2);

    component++;
    for (ll i : adj[centroid]) {
        dfs(i, centroid, costs[centroid][i], 1, 1);
        dfs(i, centroid, costs[centroid][i], 1, 0);
    }

    for (ll i : adj[centroid]) {
        adj[i].erase(centroid);
        adj[centroid].erase(i);
        process(i);
    }
}
int best_path(int n_, int k_, int edges[][2], int weights[]) {
	if (k_ == 1){
        return 0;
    }
	N = n_;
	K = k_;
	ans = 200001;
	for (int i = 0; i < N - 1; i++) {
		int u = edges[i][0];
		int v = edges[i][1];
		adj[u].insert(v);
		adj[v].insert(u);
        costs[u][v] = costs[v][u] = weights[i];
	}
    process(1);
    return (ans == 200001 ? -1 : ans);
}

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