oj.uz

Submission #537565

# Submission time Handle Problem Language Result Execution time Memory
537565 2022-03-15T08:44:42 Z topovik Parkovi (COCI22_parkovi) C++14
110 / 110
 2937 ms 68024 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 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 16 ms 23764 KB Output is correct
3 Correct 14 ms 23764 KB Output is correct
4 Correct 14 ms 23764 KB Output is correct
5 Correct 17 ms 23692 KB Output is correct
6 Correct 15 ms 23764 KB Output is correct
7 Correct 14 ms 23764 KB Output is correct
8 Correct 13 ms 23788 KB Output is correct
9 Correct 13 ms 23748 KB Output is correct
10 Correct 13 ms 23808 KB Output is correct
11 Correct 14 ms 23808 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 13 ms 23764 KB Output is correct
14 Correct 14 ms 23788 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 858 ms 53136 KB Output is correct
2 Correct 878 ms 58224 KB Output is correct
3 Correct 1704 ms 45040 KB Output is correct
4 Correct 2471 ms 37568 KB Output is correct
5 Correct 2366 ms 37172 KB Output is correct
6 Correct 2305 ms 37152 KB Output is correct
7 Correct 2244 ms 35916 KB Output is correct
8 Correct 2494 ms 36588 KB Output is correct
9 Correct 2374 ms 36948 KB Output is correct
10 Correct 2574 ms 37324 KB Output is correct
11 Correct 1514 ms 39596 KB Output is correct
12 Correct 1447 ms 39668 KB Output is correct
13 Correct 1537 ms 41416 KB Output is correct
14 Correct 1393 ms 38372 KB Output is correct
15 Correct 1363 ms 37700 KB Output is correct
16 Correct 1428 ms 39376 KB Output is correct
17 Correct 1445 ms 38416 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 831 ms 54484 KB Output is correct
2 Correct 911 ms 57856 KB Output is correct
3 Correct 839 ms 56068 KB Output is correct
4 Correct 848 ms 56076 KB Output is correct
5 Correct 915 ms 67096 KB Output is correct
6 Correct 975 ms 62396 KB Output is correct
7 Correct 969 ms 64608 KB Output is correct
8 Correct 879 ms 58388 KB Output is correct
9 Correct 879 ms 58088 KB Output is correct
10 Correct 880 ms 57392 KB Output is correct
11 Correct 854 ms 56212 KB Output is correct
12 Correct 989 ms 68024 KB Output is correct
13 Correct 954 ms 65780 KB Output is correct
14 Correct 945 ms 62420 KB Output is correct
15 Correct 832 ms 56644 KB Output is correct
16 Correct 806 ms 55272 KB Output is correct
17 Correct 830 ms 55144 KB Output is correct
18 Correct 897 ms 56904 KB Output is correct
19 Correct 943 ms 64668 KB Output is correct
20 Correct 930 ms 63340 KB Output is correct
21 Correct 835 ms 61164 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 16 ms 23764 KB Output is correct
3 Correct 14 ms 23764 KB Output is correct
4 Correct 14 ms 23764 KB Output is correct
5 Correct 17 ms 23692 KB Output is correct
6 Correct 15 ms 23764 KB Output is correct
7 Correct 14 ms 23764 KB Output is correct
8 Correct 13 ms 23788 KB Output is correct
9 Correct 13 ms 23748 KB Output is correct
10 Correct 13 ms 23808 KB Output is correct
11 Correct 14 ms 23808 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 13 ms 23764 KB Output is correct
14 Correct 14 ms 23788 KB Output is correct
15 Correct 858 ms 53136 KB Output is correct
16 Correct 878 ms 58224 KB Output is correct
17 Correct 1704 ms 45040 KB Output is correct
18 Correct 2471 ms 37568 KB Output is correct
19 Correct 2366 ms 37172 KB Output is correct
20 Correct 2305 ms 37152 KB Output is correct
21 Correct 2244 ms 35916 KB Output is correct
22 Correct 2494 ms 36588 KB Output is correct
23 Correct 2374 ms 36948 KB Output is correct
24 Correct 2574 ms 37324 KB Output is correct
25 Correct 1514 ms 39596 KB Output is correct
26 Correct 1447 ms 39668 KB Output is correct
27 Correct 1537 ms 41416 KB Output is correct
28 Correct 1393 ms 38372 KB Output is correct
29 Correct 1363 ms 37700 KB Output is correct
30 Correct 1428 ms 39376 KB Output is correct
31 Correct 1445 ms 38416 KB Output is correct
32 Correct 831 ms 54484 KB Output is correct
33 Correct 911 ms 57856 KB Output is correct
34 Correct 839 ms 56068 KB Output is correct
35 Correct 848 ms 56076 KB Output is correct
36 Correct 915 ms 67096 KB Output is correct
37 Correct 975 ms 62396 KB Output is correct
38 Correct 969 ms 64608 KB Output is correct
39 Correct 879 ms 58388 KB Output is correct
40 Correct 879 ms 58088 KB Output is correct
41 Correct 880 ms 57392 KB Output is correct
42 Correct 854 ms 56212 KB Output is correct
43 Correct 989 ms 68024 KB Output is correct
44 Correct 954 ms 65780 KB Output is correct
45 Correct 945 ms 62420 KB Output is correct
46 Correct 832 ms 56644 KB Output is correct
47 Correct 806 ms 55272 KB Output is correct
48 Correct 830 ms 55144 KB Output is correct
49 Correct 897 ms 56904 KB Output is correct
50 Correct 943 ms 64668 KB Output is correct
51 Correct 930 ms 63340 KB Output is correct
52 Correct 835 ms 61164 KB Output is correct
53 Correct 2433 ms 37396 KB Output is correct
54 Correct 2594 ms 34624 KB Output is correct
55 Correct 2597 ms 35172 KB Output is correct
56 Correct 2523 ms 35344 KB Output is correct
57 Correct 2705 ms 38872 KB Output is correct
58 Correct 2425 ms 34472 KB Output is correct
59 Correct 2786 ms 45232 KB Output is correct
60 Correct 2547 ms 34996 KB Output is correct
61 Correct 2446 ms 34084 KB Output is correct
62 Correct 2442 ms 38996 KB Output is correct
63 Correct 2654 ms 35036 KB Output is correct
64 Correct 2470 ms 44352 KB Output is correct
65 Correct 2862 ms 34764 KB Output is correct
66 Correct 2791 ms 39152 KB Output is correct
67 Correct 2608 ms 34176 KB Output is correct
68 Correct 2937 ms 45252 KB Output is correct
69 Correct 827 ms 54928 KB Output is correct
70 Correct 766 ms 53412 KB Output is correct
71 Correct 890 ms 60516 KB Output is correct
72 Correct 1485 ms 40916 KB Output is correct
73 Correct 1029 ms 41464 KB Output is correct
74 Correct 1043 ms 43004 KB Output is correct
75 Correct 1342 ms 37288 KB Output is correct
76 Correct 1450 ms 37580 KB Output is correct
77 Correct 1348 ms 37060 KB Output is correct
78 Correct 1316 ms 38736 KB Output is correct