Submission #1246712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246712		vht2025	Parkovi (COCI22_parkovi)	C++20	30 / 110	787 ms	82604 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF64 = (1LL<<62);

struct Edge{int to; ll w;};

struct TreeCenters{
    int n, LOG;
    vector<vector<Edge>> g;
    vector<vector<int>> up;
    vector<vector<ll>> jump;
    vector<int> dep;
    TreeCenters(int N, vector<vector<Edge>>&adj): n(N), g(adj){
        LOG=1; while((1<<LOG)<=n) ++LOG;
        up.assign(LOG, vector<int>(n+1,0));
        jump.assign(LOG, vector<ll>(n+1,0));
        dep.assign(n+1,0);
        build(1,0,0);
        for(int k=1;k<LOG;++k)
            for(int v=1;v<=n;++v) if(up[k-1][v]){
                up[k][v]=up[k-1][ up[k-1][v] ];
                jump[k][v]=jump[k-1][v]+jump[k-1][ up[k-1][v] ];
            }
    }
    void build(int v,int p,ll w){
        up[0][v]=p; jump[0][v]=w;
        for(auto e:g[v]) if(e.to!=p){
            dep[e.to]=dep[v]+1;
            build(e.to,v,e.w);
        }
    }
    int climb(int v,ll R){
        ll d=0;
        for(int k=LOG-1;k>=0;--k)
            if(up[k][v] && d + jump[k][v] <= R){
                d+=jump[k][v];
                v=up[k][v];
            }
        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 dep[a]>dep[b];});
        vector<char> covered(n+1,0);
        vector<int> cen;
        deque<pair<int,ll>> dq;
        for(int v:ord) if(!covered[v]){
            int c=climb(v,R); cen.push_back(c);
            dq.clear(); dq.push_back({c,0});
            while(!dq.empty()){
                auto [x,d]=dq.front(); dq.pop_front();
                if(covered[x]) continue; covered[x]=1;
                for(auto e:g[x]) if(!covered[e.to] && d+e.w<=R)
                    dq.push_back({e.to,d+e.w});
            }
        }
        return cen;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k; if(!(cin>>n>>k)) return 0;
    vector<vector<Edge>> adj(n+1);
    ll hi=0;
    for(int i=0;i<n-1;++i){
        int a,b; ll w; cin>>a>>b>>w;
        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
        hi+=w;
    }
    TreeCenters tc(n,adj);
    ll lo=0, ansR=hi;
    vector<int> ansC;
    while(lo<=hi){
        ll mid=(lo+hi)/2;
        auto tmp=tc.centers(mid);
        if((int)tmp.size()<=k){
            ansR=mid; ansC.swap(tmp); hi=mid-1;
        }else lo=mid+1;
    }
    ansC=tc.centers(ansR);            // thu lại cho bán kính tối ưu
    vector<char> mark(n+1,0);
    for(int x:ansC) mark[x]=1;
    for(int i=1;i<=n && (int)ansC.size()<k;++i)
        if(!mark[i]) ansC.push_back(i);
    cout<<ansR<<"\n";
    for(int i=0;i<k;++i) cout<<(i?" ":"")<<ansC[i];
    cout<<"\n";
    return 0;
}

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