oj.uz

Submission #533567

# Submission time Handle Problem Language Result Execution time Memory
533567 2022-03-06T10:02:58 Z topovik Parkovi (COCI22_parkovi) C++14
40 / 110
 123 ms 27480 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)
    {
        k--;
        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 39 ms 23804 KB Output is correct
2 Correct 42 ms 23788 KB Output is correct
3 Correct 36 ms 23796 KB Output is correct
4 Correct 36 ms 23796 KB Output is correct
5 Correct 39 ms 23756 KB Output is correct
6 Correct 51 ms 23764 KB Output is correct
7 Correct 47 ms 23792 KB Output is correct
8 Correct 48 ms 23756 KB Output is correct
9 Correct 109 ms 23796 KB Output is correct
10 Correct 41 ms 23804 KB Output is correct
11 Correct 67 ms 23752 KB Output is correct
12 Correct 115 ms 23792 KB Output is correct
13 Correct 40 ms 23732 KB Output is correct
14 Correct 74 ms 23756 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 25220 KB Output is correct
2 Correct 70 ms 25216 KB Output is correct
3 Incorrect 70 ms 25284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 25380 KB Output is correct
2 Correct 63 ms 25288 KB Output is correct
3 Correct 65 ms 25156 KB Output is correct
4 Correct 72 ms 25152 KB Output is correct
5 Correct 80 ms 27196 KB Output is correct
6 Correct 116 ms 26516 KB Output is correct
7 Correct 107 ms 26820 KB Output is correct
8 Correct 66 ms 25376 KB Output is correct
9 Correct 73 ms 25276 KB Output is correct
10 Correct 61 ms 25256 KB Output is correct
11 Correct 61 ms 25176 KB Output is correct
12 Correct 100 ms 27324 KB Output is correct
13 Correct 123 ms 27480 KB Output is correct
14 Correct 111 ms 27120 KB Output is correct
15 Correct 63 ms 25872 KB Output is correct
16 Correct 62 ms 25752 KB Output is correct
17 Correct 69 ms 25668 KB Output is correct
18 Correct 73 ms 25488 KB Output is correct
19 Correct 78 ms 27240 KB Output is correct
20 Correct 112 ms 27008 KB Output is correct
21 Correct 79 ms 26820 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 23804 KB Output is correct
2 Correct 42 ms 23788 KB Output is correct
3 Correct 36 ms 23796 KB Output is correct
4 Correct 36 ms 23796 KB Output is correct
5 Correct 39 ms 23756 KB Output is correct
6 Correct 51 ms 23764 KB Output is correct
7 Correct 47 ms 23792 KB Output is correct
8 Correct 48 ms 23756 KB Output is correct
9 Correct 109 ms 23796 KB Output is correct
10 Correct 41 ms 23804 KB Output is correct
11 Correct 67 ms 23752 KB Output is correct
12 Correct 115 ms 23792 KB Output is correct
13 Correct 40 ms 23732 KB Output is correct
14 Correct 74 ms 23756 KB Output is correct
15 Correct 58 ms 25220 KB Output is correct
16 Correct 70 ms 25216 KB Output is correct
17 Incorrect 70 ms 25284 KB Output isn't correct
18 Halted 0 ms 0 KB -