oj.uz

Submission #533563

# Submission time Handle Problem Language Result Execution time Memory
533563 2022-03-06T09:56:51 Z topovik Parkovi (COCI22_parkovi) C++14
10 / 110
 114 ms 25284 KB 
#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)
{
    mx++;
    ll k1 = 1, ls = 1;
    ll i = 1;
    while (i < n)
    {
        if (ls > 0)
        {
            ls += a1[i];
            if (ls > mx)
            {
                ls = -1;
                continue;
            }
        }
        else
        {
            ls -= a1[i];
            if (ls < -mx)
            {
                ls = 1;
                k1++;
            }
        }
        i++;
    }
    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;
}
/*
5 1
1 2 3
2 3 4
3 4 5
4 5 6
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 23756 KB Output is correct
2 Correct 37 ms 23784 KB Output is correct
3 Correct 36 ms 23792 KB Output is correct
4 Correct 32 ms 23756 KB Output is correct
5 Correct 34 ms 23756 KB Output is correct
6 Correct 45 ms 23808 KB Output is correct
7 Correct 44 ms 23756 KB Output is correct
8 Correct 37 ms 23784 KB Output is correct
9 Correct 114 ms 23788 KB Output is correct
10 Correct 40 ms 23788 KB Output is correct
11 Correct 65 ms 23784 KB Output is correct
12 Correct 103 ms 23756 KB Output is correct
13 Correct 35 ms 23756 KB Output is correct
14 Correct 73 ms 23784 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 25228 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 25284 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 23756 KB Output is correct
2 Correct 37 ms 23784 KB Output is correct
3 Correct 36 ms 23792 KB Output is correct
4 Correct 32 ms 23756 KB Output is correct
5 Correct 34 ms 23756 KB Output is correct
6 Correct 45 ms 23808 KB Output is correct
7 Correct 44 ms 23756 KB Output is correct
8 Correct 37 ms 23784 KB Output is correct
9 Correct 114 ms 23788 KB Output is correct
10 Correct 40 ms 23788 KB Output is correct
11 Correct 65 ms 23784 KB Output is correct
12 Correct 103 ms 23756 KB Output is correct
13 Correct 35 ms 23756 KB Output is correct
14 Correct 73 ms 23784 KB Output is correct
15 Incorrect 62 ms 25228 KB Unexpected end of file - int32 expected
16 Halted 0 ms 0 KB -