Submission #537565

#	Time	Username	Problem	Language	Result	Execution time	Memory
537565		topovik	Parkovi (COCI22_parkovi)	C++14	110 / 110	2937 ms	68024 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second

using namespace std;

typedef long long ll;
typedef long double ld;

const ll N = 1e6 + 100;
const ll M = 1e3 + 10;
const ll oo = 1e18 + 7;

vector <pair<ll, ll> > a[N];

ll n, k;
ll mx_ds;
ll kol;
pair<ll, ll> dp[N];

set <ll> ans;
bool g = 0;

pair<ll, ll> Rec(ll x, ll y)
{
    vector <pair<ll, ll> > vc;
    ll up = 0;
    for (auto i : a[x])
        if (i.f != y) vc.pb(Rec(i.f, x));
        else up = i.s;
    sort(vc.begin(), vc.end());
    ll mx = 0;
    ll mn = (vc.size() > 0 ? vc[0].f : oo);
    for (auto i : vc)
        if (mn + i.s > mx_ds) mx = max(mx, i.s);
//    for (auto i : vc) cout << i.f << " " << i.s << endl;
//    cout << mx << " " << mn << endl;
//    system("pause");
    if (mx + up > mx_ds && (mx != 0 || mn > mx_ds))
    {
        if (g) ans.insert(x);
        kol++;
        mx = 0;
        mn = 0;
    }
    if (x == 0 && (mx != 0 || mn > mx_ds))
    {
        if (g) ans.insert(x);
        kol++;
        return {0, 0};
    }

    mx += up;
    if (mx == up && mn <= mx_ds) mx = 0;
    mn += up;
    if (mn > mx_ds) mn = oo;
    return {mn, mx};
}

bool Check(ll x)
{
    mx_ds = x;
    kol = 0;
    Rec(0, 0);
    return kol <= k;
}

int main()
{
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (ll i = 0; i < n - 1; i++)
    {
        ll x, y, z;
        cin >> x >> y >> z;
        a[--x].pb({--y, z});
        a[y].pb({x, z});
    }
    ll l = 0, r = oo;
    while (l < r)
    {
        ll mdl = (l + r) >> 1;
        if (Check(mdl)) r = mdl;
        else l = mdl + 1;
    }
    cout << l << endl;
    g = 1;
    Check(l);
    ll i = 0;
    while (ans.size() < k) ans.insert(i++);
    for (auto i : ans) cout << i + 1 << " ";
}
/*
5 1
1 2 3
2 3 4
3 4 5
4 5 6
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:94:23: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   94 |     while (ans.size() < k) ans.insert(i++);
      |            ~~~~~~~~~~~^~~

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