제출 #1246731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246731		vht2025	Parkovi (COCI22_parkovi)	C++20	0 / 110	266 ms	68456 KiB

Main

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

struct Parkovi {
    int n, LOG;
    vector<vector<Edge>> g;
    vector<vector<int>> up;
    vector<vector<ll>> jump;
    vector<ll> dist;
    vector<int> order;          // đỉnh theo distRoot giảm dần
    vector<int> parent;
    vector<ll> wpar;

    Parkovi(int N): n(N) {
        g.assign(n+1,{});
        LOG = 1; while((1<<LOG) <= n) ++LOG;
        up.assign(LOG, vector<int>(n+1));
        jump.assign(LOG, vector<ll>(n+1));
        dist.assign(n+1,0);
        parent.assign(n+1,0);
        wpar.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){
        parent[v]=p; wpar[v]=w;
        up[0][v]=p;   jump[0][v]=w;
        for(auto e:g[v]) if(e.to!=p){
            dist[e.to]=dist[v]+e.w;
            dfs(e.to,v,e.w);
        }
    }
    void build(){
        dfs(1,0,0);
        for(int k=1;k<LOG;++k)
            for(int v=1;v<=n;++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] ];
            }
        order.resize(n);
        iota(order.begin(),order.end(),1);
        sort(order.begin(),order.end(),
             [&](int a,int b){return dist[a]>dist[b];});
    }
    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,int kLimit){
        static vector<char> covered; if(covered.size()!=n+1) covered.assign(n+1,0);
        static vector<int> vis;      if(vis.size()!=n+1)      vis.assign(n+1,0);
        fill(covered.begin(),covered.end(),0);
        int stamp = 0;
        vector<int> res;
        deque<pair<int,ll>> dq;

        for(int v:order){
            if(covered[v]) continue;
            if((int)res.size() > kLimit) return res; // early stop
            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;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k; if(!(cin>>n>>k)) return 0;
    Parkovi P(n);
    for(int i=0;i<n-1;++i){
        int a,b; ll w; cin>>a>>b>>w;
        P.addEdge(a,b,w);
    }
    P.build();

    ll hi = *max_element(P.dist.begin()+1,P.dist.end()); // ≥ đáp án
    ll lo = 0, bestR = hi;
    vector<int> bestC;
    while(lo<=hi){
        ll mid = (lo+hi)/2;
        auto tmp = P.centers(mid,k);
        if((int)tmp.size() <= k){
            bestR = mid; bestC.swap(tmp); hi = mid-1;
        }else lo = mid+1;
    }
    bestC = P.centers(bestR,k);
    vector<char> mark(n+1,0);
    for(int x:bestC) mark[x]=1;
    for(int i=1;i<=n && (int)bestC.size()<k;++i)
        if(!mark[i]) bestC.push_back(i);

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

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