Submission #1161203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161203		12345678	Parkovi (COCI22_parkovi)	C++17	110 / 110	706 ms	41240 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5;

ll n, k, lst[nx], far[nx], u, v, w, dist[nx], l=0, r=1e18, md, cnt, fil[nx];
vector<pair<ll, ll>> d[nx];
vector<ll> res;

void dfs(ll u, ll p, ll lstw)
{
    int c=0;
    lst[u]=far[u]=-1;
    for (auto [v, w]:d[u])
    {
        if (v==p) continue;
        dist[v]=dist[u]+w;
        dfs(v, u, w);
        c++;
        if (far[v]!=-1&&(far[u]==-1||dist[far[v]]>dist[far[u]])) far[u]=far[v];
        if (lst[v]!=-1&&(lst[u]==-1||dist[lst[v]]<dist[lst[u]])) lst[u]=lst[v];
    }
    if (c==0) far[u]=u;
    if (lst[u]!=-1&&far[u]!=-1&&dist[lst[u]]+dist[far[u]]-2*dist[u]<=md) far[u]=-1;
    if (far[u]==-1&&lst[u]!=-1&&dist[lst[u]]-dist[u]>md) far[u]=u;
    if (far[u]!=-1&&dist[far[u]]-dist[u]+lstw>md) cnt++, res.push_back(u), far[u]=-1, lst[u]=u;
    if (u==p&&far[u]!=-1) cnt++, res.push_back(u);

}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1; i<n; i++) cin>>u>>v>>w, d[u].push_back({v, w}), d[v].push_back({u, w});
    while (l<r)
    {
        md=(l+r)/2;
        res.clear();
        cnt=0;
        dfs(1, 1, 0);
        //cout<<"debug "<<md<<' '<<cnt<<'\n';
        if (cnt<=k) r=md;
        else l=md+1;
    }
    res.clear();
    md=l;
    dfs(1, 1 ,0);
    cout<<md<<'\n';
    for (auto x:res) fil[x]=1;
    for (int i=1; i<=n; i++) if (res.size()<k&&!fil[i]) res.push_back(i);
    for (auto x:res) cout<<x<<' '; 
}

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