oj.uz

Submission #533566

# Submission time Handle Problem Language Result Execution time Memory
533566 2022-03-06T10:02:02 Z topovik Parkovi (COCI22_parkovi) C++14
10 / 110
 352 ms 93256 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];
int used[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 << " ";
                    k--;
                    used[i] = 1;
                }
                ls = -1;
                continue;
            }
        }
        else
        {
            ls -= a1[i];
            if (ls < -mx)
            {
                ls = 1;
                k1++;
            }
        }
        i++;
    }
    if (pr && ls > 0)
    {
        cout << i << " ";
        k--;
        used[i] = 1;
    }
    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);
    int ls = 1;
    while (k > 0)
    {
        while (used[ls]) ls++;
        cout << ls << " ";
        used[ls] = 1;
    }
}
/*
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 27 ms 23756 KB Output is correct
2 Correct 29 ms 23724 KB Output is correct
3 Correct 29 ms 23812 KB Output is correct
4 Correct 37 ms 23800 KB Output is correct
5 Correct 30 ms 23784 KB Output is correct
6 Correct 57 ms 23804 KB Output is correct
7 Correct 47 ms 23756 KB Output is correct
8 Correct 32 ms 23808 KB Output is correct
9 Correct 94 ms 23756 KB Output is correct
10 Correct 31 ms 23756 KB Output is correct
11 Correct 63 ms 23788 KB Output is correct
12 Correct 136 ms 23796 KB Output is correct
13 Correct 38 ms 23804 KB Output is correct
14 Correct 57 ms 23756 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 25232 KB Output is correct
2 Correct 64 ms 25220 KB Output is correct
3 Incorrect 75 ms 25272 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 25284 KB Output is correct
2 Correct 64 ms 25284 KB Output is correct
3 Correct 73 ms 25340 KB Output is correct
4 Correct 78 ms 25104 KB Output is correct
5 Correct 89 ms 27204 KB Output is correct
6 Correct 102 ms 26612 KB Output is correct
7 Correct 129 ms 26696 KB Output is correct
8 Correct 64 ms 25308 KB Output is correct
9 Correct 66 ms 25376 KB Output is correct
10 Correct 71 ms 25284 KB Output is correct
11 Correct 64 ms 25168 KB Output is correct
12 Runtime error 352 ms 93256 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 23756 KB Output is correct
2 Correct 29 ms 23724 KB Output is correct
3 Correct 29 ms 23812 KB Output is correct
4 Correct 37 ms 23800 KB Output is correct
5 Correct 30 ms 23784 KB Output is correct
6 Correct 57 ms 23804 KB Output is correct
7 Correct 47 ms 23756 KB Output is correct
8 Correct 32 ms 23808 KB Output is correct
9 Correct 94 ms 23756 KB Output is correct
10 Correct 31 ms 23756 KB Output is correct
11 Correct 63 ms 23788 KB Output is correct
12 Correct 136 ms 23796 KB Output is correct
13 Correct 38 ms 23804 KB Output is correct
14 Correct 57 ms 23756 KB Output is correct
15 Correct 57 ms 25232 KB Output is correct
16 Correct 64 ms 25220 KB Output is correct
17 Incorrect 75 ms 25272 KB Output isn't correct
18 Halted 0 ms 0 KB -