Submission #935225

#	Time	Username	Problem	Language	Result	Execution time	Memory
935225		Bula	Race (IOI11_race)	C++17	100 / 100	1915 ms	77868 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int mod = 1e9 + 7, N = 2e5 + 5;
int n, k, ans = INT_MAX;
vector<int> adj[N], subtree_size(N);
vector<bool> is_removed(N);
vector<pair<int, int>> cur;
map<pair<int, int>, int> l;
void dfs(int v, int par, int dist, int edge){
    if(dist > k || edge > ans) return;
    cur.push_back({dist, edge});
    for(auto to : adj[v]){
        if(to == par || is_removed[to]) continue;
        dfs(to, v, dist + l[{v, to}], edge + 1);
    }
}

int get_subtree_size(int node, int parent = -1) {
	subtree_size[node] = 1;
	for (int child : adj[node]) {
		if (child == parent || is_removed[child]) { continue; }
		subtree_size[node] += get_subtree_size(child, node);
	}
	return subtree_size[node];
}

int get_centroid(int node, int tree_size, int parent = -1) {
	for (int child : adj[node]) {
		if (child == parent || is_removed[child]) { continue; }
		if (subtree_size[child] * 2 > tree_size) {
			return get_centroid(child, tree_size, node);
		}
	}
	return node;
}

void build_centroid_decomp(int node = 0) {
	int centroid = get_centroid(node, get_subtree_size(node));

	map<int, int> mp;
	for(int x : adj[centroid]){
	    if(is_removed[x]) continue;
	    dfs(x, centroid, l[{centroid, x}], 1);
	    for(auto pr : cur){
	        if(pr.first == k) ans = min(ans, pr.second);
            else if(mp.find(k - pr.first) != mp.end()){
	            ans = min(ans, mp[k - pr.first] + pr.second);
            }
        }
        for(auto pr : cur){
            if(mp.find(pr.first) == mp.end()){
                mp[pr.first] = pr.second;
            }else mp[pr.first] = min(mp[pr.first], pr.second);
        }
        cur.clear();
    }

	is_removed[centroid] = true;

	for (int child : adj[centroid]) {
		if (is_removed[child]) { continue; }
		build_centroid_decomp(child);
	}
}

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 x = H[i][0], y = H[i][1];
        adj[x].push_back(y);
        adj[y].push_back(x);
        l[{x, y}] = l[{y, x}] = L[i];
    }
    build_centroid_decomp();
    return (ans == INT_MAX ? -1 : ans);
}

//main(){
//    ios::sync_with_stdio(0);
//    cin.tie(0),cout.tie(0);
//    int tt = 1; //cin >> tt;
//    while(tt--){
//        int N, K;
//        cin >> N >> K;
//        int H[N][2], L[N];
//        for(int i = 0; i < N - 1; i++){
//            cin >> H[i][0] >> H[i][1];
//        }
//        for(int i = 0; i < N - 1; i++){
//            cin >> L[i];
//        }
//        cout << best_path(N, K, H, L) << endl;
//    }
//}

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