Submission #1309620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309620		vk3601h	Race (IOI11_race)	C++20	0 / 100	1 ms	332 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;

class Solver{
private:
    vector<vector<int>> &adj;
    map<pair<int, int>, long long> &weight;
    vector<int> subtree_size;
    vector<bool> is_removed;

    long long goal;
    int res;

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

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

    void build_centroid_decomp(int curr = 0){
        int centroid = get_centroid(curr, get_subtree_size(curr));
        is_removed[centroid] = true;

        map<long long, int> cnt;
        cnt[0] = 1;
        for (int child : adj[centroid]){
            if (!is_removed[child]){
                dfs(child, centroid, 1, weight[make_pair(centroid, child)], true, cnt);
                dfs(child, centroid, 1, weight[make_pair(centroid, child)], false, cnt);
            }
        }

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

    void dfs(int curr, int parent, int depth, long long dist, bool type, map<long long, int> &cnt){
        if (dist > goal) return;
        if (type) if (cnt.find(goal - dist) != cnt.end()) res = min(res, depth + cnt[goal - dist]);
        else {
            if (cnt.find(dist) == cnt.end()) cnt[dist] = depth;
            else cnt[dist] = min(cnt[dist], depth);
        }

        for (int child : adj[curr]){
            if (child == parent || is_removed[child]) continue;
            dfs(child, curr, depth + 1, dist + weight[make_pair(curr, child)], type, cnt);
        }
    }

public:
    Solver(vector<vector<int>> &_adj, map<pair<int, int>, long long> &_weight, long long _goal) : adj(_adj), weight(_weight), subtree_size(adj.size()), is_removed(adj.size(), false), goal(_goal), res(INT_MAX) {
        build_centroid_decomp();
    }

    int get_res() {return res;}
};

int best_path(int N, int K, int H[][2], int L[]){
    vector<vector<int>> adj(N);
    map<pair<int, int>, long long> weight;
    for (int i = 0; i < N - 1; i++){
        int u = H[i][0], v = H[i][1];
        long long w = L[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
        weight[make_pair(u, v)] = w;
        weight[make_pair(v, u)] = w;
    }

    Solver solver(adj, weight, K);
    int res = solver.get_res();
    return res < INT_MAX ? res : -1;
}

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