Submission #533564

#	Time	Username	Problem	Language	Result	Execution time	Memory
533564		topovik	Parkovi (COCI22_parkovi)	C++14	10 / 110	109 ms	27036 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 oo = 1e18 + 10;

const ll N = 1e6 + 10;
const ll M1 = 1e6;

ll n, k;
ll a1[N];

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

bool Check(ll mx, bool pr = 0)
{
    mx++;
    ll k1 = 1, ls = 1;
    ll i = 1;
    while (i < n)
    {
        if (ls > 0)
        {
            ls += a1[i];
            if (ls > mx)
            {
                if (pr) cout << i << " ";
                ls = -1;
                continue;
            }
        }
        else
        {
            ls -= a1[i];
            if (ls < -mx)
            {
                ls = 1;
                k1++;
            }
        }
        i++;
    }
    if (pr && ls > 0) cout << n;
    return k1 <= k;
}

void Rec(ll x, ll y, ll ds)
{
    mn[x] = min(mn[x], ds);
    for (auto i : a[x])
        if (i.f != y)
    {
        Rec(i.f, x, ds + i.s);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    if (n <= 20)
    {
        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 ans = oo, nom = 0;
        for (ll msk = (1 << n) - 1; msk >= 0; msk--)
        {
            ll k1 = 0;
            for (ll j = 0; j < n; j++)
                if ((msk >> j) & 1) k1++;
            if (k1 != k) continue;
            for (ll j = 0; j < n; j++) mn[j] = oo;
            for (ll j = 0; j < n; j++)
                if ((msk >> j) & 1) Rec(j, j, 0);
            ll mx = 0;
            for (ll j = 0; j < n; j++) mx = max(mx, mn[j]);
            if (mx < ans) ans = mx, nom = msk;
        }
        cout << ans << endl;
        for (int i = 0; i < n; i++)
            if ((nom >> i) & 1) cout << i + 1 << " ";
        cout << endl;
        return 0;
    }
    for (ll i = 1; i < n; i++)
    {
        cin >> a1[i] >> a1[i] >> a1[i];
    }
    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;
    Check(l, 1);
}
/*
5 1
1 2 3
2 3 4
3 4 5
4 5 6
*/

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