Submission #1294677

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

race

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

using pii = pair<int,int>; // {weight, edges}
const int INF = 1e7;

vector<vector<pair<int,int>>> g;
vector<int> sz;
vector<bool> vis;
int ans;

void dfs_sz(int u, int p){
    sz[u] = 1;
    for(auto [v,w]: g[u]){
        if(v==p || vis[v]) continue;
        dfs_sz(v,u);
        sz[u] += sz[v];
    }
}

int get_centroid(int u, int tot, int p){
    for(auto [v,w]: g[u]){
        if(v==p || vis[v]) continue;
        if(sz[v]*2 > tot) return get_centroid(v, tot, u);
    }
    return u;
}

// collect all (weight, edges) from u
void collect(int u, int p, int d, int w, vector<pii> &nodes){
    nodes.push_back({w,d});
    for(auto [v,wt]: g[u]){
        if(v==p || vis[v]) continue;
        collect(v,u,d+1,w+wt,nodes);
    }
}

// merge two vectors of {weight,edges}, keeping minimal edges per weight
// used to maintain sparse min_edges
void merge(vector<pii> &big, const vector<pii> &small, int K){
    vector<pii> temp;
    temp.reserve(big.size() + small.size());
    for(auto x: big) temp.push_back(x);
    for(auto x: small) temp.push_back(x);

    sort(temp.begin(), temp.end());
    vector<pii> res;
    int best = INF;
    for(auto [w,e]: temp){
        if(w > K) continue;
        if(e < best){
            best = e;
            res.push_back({w,best});
        }
    }
    big = move(res);
}

void solve(int u, int K){
    dfs_sz(u,-1);
    int c = get_centroid(u, sz[u], -1);
    vis[c] = true;

    vector<pii> merged; // sparse min_edges, initially empty
    merged.push_back({0,0}); // distance 0 with 0 edges

    for(auto [v,w]: g[c]){
        if(vis[v]) continue;
        vector<pii> subtree;
        collect(v,c,1,w,subtree);

        // query all pairs from subtree and merged to see if total weight == K
        for(auto [sw,se]: subtree){
            int rem = K - sw;
            // binary search merged
            auto it = upper_bound(merged.begin(), merged.end(), make_pair(rem,INF));
            if(it != merged.begin()){
                --it;
                int total_edges = se + it->second;
                ans = min(ans,total_edges);
            }
        }

        // merge subtree into merged
        merge(merged,subtree,K);
    }

    for(auto [v,w]: g[c]){
        if(!vis[v]) solve(v,K);
    }
}

int best_path(int N,int K,int H[][2], int L[]){
    g.assign(N,{});
    sz.assign(N,0);
    vis.assign(N,false);
    ans = INF;
    for(int i=0;i<N-1;i++){
        g[H[i][0]].push_back({H[i][1],L[i]});
        g[H[i][1]].push_back({H[i][0],L[i]});
    }
    solve(0,K);
    if(ans>=INF) return -1;
    return ans;
}

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