Submission #533524

#	Time	Username	Problem	Language	Result	Execution time	Memory
533524		Vimmer	Parkovi (COCI22_parkovi)	C++14	110 / 110	2085 ms	46348 KiB

Main

#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")

#define F first
#define S second
#define PB push_back
#define M ll(1e9 + 7)
#define sz(x) int(x.size())
#define N 200005
#define pri(x) cout << x << endl
//#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define _ << " " <<

using namespace std;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef short int si;
typedef unsigned long long ull;

int n, k;

vector <pair <int, int> > g[N];

bool go;

ll md;

int ost;

bool cmp(pair <ll, ll> x, pair <ll, ll> y)
{
    return x.S < y.S;
}

set <int> ans;

pair <ll, ll> dfs(int v, int p, ll dst)
{
    ll mx = 0;

    ll when = 1e18;

    vector <pair <ll, ll> > vr; vr.clear();

    for (auto it : g[v])
    {
        if (it.F == p)
            continue;

        pair <ll, ll> vl = dfs(it.F, v, it.S);

        vr.PB(vl);
    }

    sort(all(vr), cmp);

    for (int i = 0; i < sz(vr); i++)
    {
        if (vr[0].S + vr[i].F > md)
            mx = max(mx, vr[i].F);
    }

    if (sz(vr))
        when = vr[0].S;

//    pri(v _ mx _ when _ ost _ dst);

    if (mx + dst > md && (mx != 0 || when > md))
    {
        if (go)
            ans.insert(v);

        ost--;

        when = 0;

        mx = 0;
    }

    if (v == 1 && (mx != 0 || when > md))
    {
        ost--;

        return {mx, when};
    }

//    pri(v _ mx _ when _ ost _ dst);
    mx += dst;

    if (mx == dst && when <= md)
        mx = 0;

    if (when != 1e18)
        when += dst;

    if (when > md)
        when = 1e18;

    return {mx, when};
}

int main()
{
    istream::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("1.in", "r", stdin);

    cin >> n >> k;

    for (int i = 1; i < n; i++)
    {
        int x, y, w;

        cin >> x >> y >> w;

        g[x].PB({y, w});

        g[y].PB({x, w});
    }

    ll l = 1, r = 1e18;

    while (l < r)
    {
        md = (l + r) / 2;

        ost = k;

        dfs(1, -1, 0);

        if (ost >= 0)
            r = md;
                else l = md + 1;
    }

    md = l;

    go = 1;

    dfs(1, -1, 0);

    pri(l);

    int i = 1;

    while (sz(ans) < k)
    {
        ans.insert(i++);
    }

    for (auto it : ans)
        cout << it << " ";
}

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