Submission #534934

#	Time	Username	Problem	Language	Result	Execution time	Memory
534934		N1NT3NDO	Parkovi (COCI22_parkovi)	C++17	110 / 110	1583 ms	31600 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

using namespace std;
//using namespace __gnu_pbds;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = (int)2e5 + 500;
vector< pair<int, int> > g[N];
ll dp_down[N], dp_up[N], cur;
int n, k;
vector<int> ans;
bool used[N];

void dfs(int v, int pr, ll d)
{
    dp_down[v] = 1e18;
    dp_up[v] = 0;
    for(const auto &[u, w] : g[v])
    {
        if (u == pr) continue;
        dfs(u, v, w);
        dp_down[v] = min(dp_down[v], dp_down[u]);
        dp_up[v] = max(dp_up[v], dp_up[u]);
    }

    if (dp_down[v] + dp_up[v] <= cur)
      dp_up[v] = -1e18;

    if (dp_up[v] != -1e18 && (pr == -1 || dp_up[v] + d > cur))
    {
        dp_down[v] = 0;
        dp_up[v] = -1e18;
        ans.pb(v);
    }

    dp_down[v] += d; dp_up[v] += d;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i < n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }

    ll l = 0, r = 2e14;

    while(l < r)
    {
        ll m = (l + r) / 2ll;
        cur = m;
        ans.clear();
        dfs(1, -1, 0);

        if (sz(ans) <= k) r = m;
        else l = m + 1;
    }

    cur = l;
    ans.clear();
    dfs(1, -1, 0);

    cout << l << '\n';
    for(auto &u : ans) used[u] = 1;
    for(int i = 1; i <= n; i++)
      if (sz(ans) < k && !used[i])
        {
            ans.pb(i);
        }

    for(auto u : ans) cout << u << ' ';
}

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