제출 #1246730

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246730		vht2025	Parkovi (COCI22_parkovi)	C++20	50 / 110	3093 ms	69172 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge{int to; ll w;};

struct Solver{
    int n, LOG;
    vector<vector<Edge>> g;
    vector<vector<int>> up;
    vector<vector<ll>> jump;
    vector<ll> dist;
    Solver(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));
        dist.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 dfs(int v,int p,ll w,ll acc){
        up[0][v]=p; jump[0][v]=w; dist[v]=acc;
        for(auto e:g[v]) if(e.to!=p)
            dfs(e.to,v,e.w,acc+e.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];
            }
    }
    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 dist[a]>dist[b];});
        vector<char> covered(n+1,0);
        vector<int> vis(n+1,0);
        int stamp = 1;
        vector<int> res;
        deque<pair<int,ll>> dq;
        for(int v:ord) if(!covered[v]){
            int c = climb(v,R);
            res.push_back(c);
            ++stamp; dq.clear(); dq.push_back({c,0});
            while(!dq.empty()){
                auto [u,d]=dq.front(); dq.pop_front();
                if(d>R || vis[u]==stamp) continue;
                vis[u]=stamp; covered[u]=1;
                for(auto e:g[u])
                    if(d+e.w<=R) dq.push_back({e.to,d+e.w});
            }
        }
        return res;
    }
    pair<ll,vector<int>> solve(int k){
        ll lo=0, hi=0;
        for(int v=2; v<=n; ++v) hi = max<ll>(hi, dist[v]); // upper bound
        vector<int> best;
        while(lo<=hi){
            ll mid=(lo+hi)/2;
            auto c=centers(mid);
            if((int)c.size()<=k){ best.swap(c); hi=mid-1; }
            else lo=mid+1;
        }
        auto finalC = centers(lo);
        vector<char> mark(n+1,0);
        for(int x:finalC) mark[x]=1;
        for(int i=1;i<=n && (int)finalC.size()<k;++i)
            if(!mark[i]) finalC.push_back(i);
        return {lo, finalC};
    }
};

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n,k; if(!(cin>>n>>k)) return 0;
    Solver S(n);
    ll sumW=0;
    for(int i=0;i<n-1;++i){
        int a,b; ll w; cin>>a>>b>>w;
        S.addEdge(a,b,w); sumW+=w;
    }
    S.build();
    auto [R,ans]=S.solve(k);
    cout<<R<<"\n";
    for(int i=0;i<k;++i) cout<<(i?" ":"")<<ans[i];
    cout<<"\n";
    return 0;
}

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