Submission #1264435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264435		piolk	Race (IOI11_race)	C++20	0 / 100	0 ms	328 KiB

race

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

vector<vector<pair<int,int>>> tree;
vector<int> subSizes;
vector<bool> removed;

int K;
int ans=INT_MAX;

int getSubSize(int node,int parent){
    subSizes[node]=1;
    for (auto [child,cost]:tree[node]){
        if (child==parent || removed[child]) continue;
        subSizes[node]+=getSubSize(child,node);
    }
    return subSizes[node];
}

int getCentroid(int node,int parent,int subSize){
    for (auto [child,cost]:tree[node]){
        if (child==parent || removed[child]) continue;

        if (subSizes[child]*2>subSize) return getCentroid(child,node,subSize);
    }
    return node;
}

void getPaths(int node,int parent,int centroid,int dist,int edges,vector<pair<int,int>> &distances){
    if (dist>K) return;
    distances.emplace_back(dist,edges);

    for (auto [child,cost]:tree[node]){
        if (child==parent || removed[child]) continue;
        getPaths(child,node,centroid,dist+cost,edges+1,distances);
    }
}

void process(int centroid){
    vector<int> dists(K+7); //sum, edges

    for (auto [child,cost]:tree[centroid]){
        if (removed[child]) continue;

        // potrzebuje wszystkie sciezki
        vector<pair<int,int>> distances;
        getPaths(child,centroid,centroid,cost,1,distances);

        for (auto [sum,edges]:distances){
            if (dists[K-sum]>0){
                ans=min(ans,dists[K-sum]+edges);
            }
        }
        for (auto [sum,edges]:distances){
            if (dists[sum]==0) dists[sum]=edges;
            else dists[sum]=min(dists[sum],edges);
        }
    }
}

void decomp(int node){
    int centroid=getCentroid(node,-1,getSubSize(node,-1));
    process(centroid);
    removed[centroid]=true;
    for (auto [child,cost]:tree[centroid]){
        if (removed[child]) continue;
        decomp(child);
    }
}

int best_path(int n,int k,int h[][2],int l[]){
    ans=INT_MAX;
    K=k;
    tree.clear();
    subSizes.clear();
    removed.clear();

    tree.resize(n+1);
    subSizes.resize(n+1);
    removed.resize(n+1);

    for (int i=0;i<n-1;i++){
        int u=h[i][0];
        int v=h[i][1];

        int price=l[i];
        tree[u].emplace_back(v,price);
        tree[v].emplace_back(u,price);
    }

    decomp(1);

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

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