Submission #1246723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246723		vht2025	Parkovi (COCI22_parkovi)	C++20	40 / 110	1277 ms	69556 KiB

Main

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

struct Edge {int to; ll w;};

struct Park {
    int n, LOG;
    vector<vector<Edge>> g;
    vector<vector<int>> up;
    vector<vector<ll>> jump;
    vector<ll> distRoot;

    Park(int N): n(N) {
        g.assign(n+1, {});
        LOG = 1; while((1<<LOG) <= n) ++LOG;
        up.assign(LOG, vector<int>(n+1, 0));
        jump.assign(LOG, vector<ll>(n+1, 0));
        distRoot.assign(n+1, 0);
    }
    void addEdge(int u,int v,ll w){
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    void build(){
        dfs(1,0,0,0);
        for(int k=1;k<LOG;++k)
            for(int v=1;v<=n;++v){
                int a = up[k-1][v];
                up[k][v] = up[k-1][a];
                jump[k][v] = jump[k-1][v] + jump[k-1][a];
            }
    }
    void dfs(int v,int p,ll w,ll acc){
        up[0][v]=p; jump[0][v]=w; distRoot[v]=acc;
        for(auto e:g[v]) if(e.to!=p)
            dfs(e.to,v,e.w,acc+e.w);
    }
    int climb(int v,ll R){
        ll d=0;
        for(int k=LOG-1;k>=0;--k){
            int a = up[k][v];
            if(a && d + jump[k][v] <= R){
                d += jump[k][v];
                v = a;
            }
        }
        return v;
    }
    vector<int> centers(ll R){
        vector<int> ord(n); iota(ord.begin(),ord.end(),1);
        sort(ord.begin(),ord.end(),
             [&](int a,int b){return distRoot[a]>distRoot[b];});

        vector<char> covered(n+1,0), seen(n+1,0);
        vector<int> res;
        deque<pair<int,ll>> dq;

        for(int v:ord) if(!covered[v]){
            int c = climb(v,R);
            res.push_back(c);

            dq.clear(); dq.push_back({c,0});
            while(!dq.empty()){
                auto [x,d] = dq.front(); dq.pop_front();
                if(d > R || seen[x]) continue;
                seen[x]=1; covered[x]=1;
                for(auto e:g[x])
                    if(d + e.w <= R) dq.push_back({e.to,d+e.w});
            }
        }
        return res;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k; if(!(cin>>n>>k)) return 0;
    Park T(n);
    ll hi=0;
    for(int i=0;i<n-1;++i){
        int u,v; ll w; cin>>u>>v>>w;
        T.addEdge(u,v,w); hi+=w;
    }
    T.build();

    ll lo=0, ansR=hi;
    vector<int> bestC;
    while(lo<=hi){
        ll mid=(lo+hi)/2;
        auto C = T.centers(mid);
        if((int)C.size() <= k){
            ansR = mid; bestC.swap(C);
            hi = mid-1;
        }else lo = mid+1;
    }
    // lấy lại chính xác k công viên
    bestC = T.centers(ansR);
    vector<char> used(n+1,0);
    for(int x:bestC) used[x]=1;
    for(int i=1; i<=n && (int)bestC.size()<k; ++i)
        if(!used[i]) bestC.push_back(i);

    cout<<ansR<<"\n";
    for(int i=0;i<k;++i)
        cout<<(i?" ":"")<<bestC[i];
    cout<<"\n";
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 0 / 60