oj.uz

Submission #534933

# Submission time Handle Problem Language Result Execution time Memory
534933 2022-03-09T07:13:56 Z N1NT3NDO Parkovi (COCI22_parkovi) C++14
110 / 110
 1994 ms 33044 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

using namespace std;
//using namespace __gnu_pbds;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = (int)2e5 + 500;
vector< pair<int, int> > g[N];
ll dp_down[N], dp_up[N], cur;
int n, k;
vector<int> ans;
bool used[N];

void dfs(int v, int pr, ll d)
{
    dp_down[v] = 1e18;
    dp_up[v] = 0;
    for(auto [u, w] : g[v])
    {
        if (u == pr) continue;
        dfs(u, v, w);
        dp_down[v] = min(dp_down[v], dp_down[u]);
        dp_up[v] = max(dp_up[v], dp_up[u]);
    }

    if (dp_down[v] + dp_up[v] <= cur)
      dp_up[v] = -1e18;

    if (dp_up[v] != -1e18 && (pr == -1 || dp_up[v] + d > cur))
    {
        dp_down[v] = 0;
        dp_up[v] = -1e18;
        ans.pb(v);
    }

    dp_down[v] += d; dp_up[v] += d;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i < n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }

    ll l = 0, r = 2e14;

    while(l < r)
    {
        ll m = (l + r) / 2ll;
        cur = m;
        ans.clear();
        dfs(1, -1, 0);

        if (sz(ans) <= k) r = m;
        else l = m + 1;
    }

    cur = l;
    ans.clear();
    dfs(1, -1, 0);

    cout << l << '\n';
    for(auto u : ans) used[u] = 1;
    for(int i = 1; i <= n; i++)
      if (sz(ans) < k && !used[i])
        {
            ans.pb(i);
        }

    for(auto u : ans) cout << u << ' ';
}

Compilation message

Main.cpp: In function 'void dfs(int, int, long long int)':
Main.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for(auto [u, w] : g[v])
      |              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 3 ms 5028 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 5040 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 4 ms 5032 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 5036 KB Output is correct
12 Correct 3 ms 5032 KB Output is correct
13 Correct 3 ms 4996 KB Output is correct
14 Correct 3 ms 5012 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 29964 KB Output is correct
2 Correct 364 ms 30420 KB Output is correct
3 Correct 430 ms 17732 KB Output is correct
4 Correct 1272 ms 16328 KB Output is correct
5 Correct 1187 ms 16020 KB Output is correct
6 Correct 1182 ms 16104 KB Output is correct
7 Correct 1194 ms 16124 KB Output is correct
8 Correct 1355 ms 16740 KB Output is correct
9 Correct 1303 ms 16416 KB Output is correct
10 Correct 1337 ms 16644 KB Output is correct
11 Correct 882 ms 17500 KB Output is correct
12 Correct 815 ms 17600 KB Output is correct
13 Correct 860 ms 18644 KB Output is correct
14 Correct 793 ms 17460 KB Output is correct
15 Correct 820 ms 17056 KB Output is correct
16 Correct 792 ms 17684 KB Output is correct
17 Correct 821 ms 17056 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 30928 KB Output is correct
2 Correct 347 ms 30260 KB Output is correct
3 Correct 344 ms 29124 KB Output is correct
4 Correct 333 ms 28992 KB Output is correct
5 Correct 412 ms 31984 KB Output is correct
6 Correct 395 ms 31472 KB Output is correct
7 Correct 437 ms 32388 KB Output is correct
8 Correct 359 ms 31140 KB Output is correct
9 Correct 393 ms 30888 KB Output is correct
10 Correct 332 ms 30400 KB Output is correct
11 Correct 340 ms 29508 KB Output is correct
12 Correct 398 ms 33044 KB Output is correct
13 Correct 422 ms 32908 KB Output is correct
14 Correct 399 ms 31960 KB Output is correct
15 Correct 330 ms 30404 KB Output is correct
16 Correct 346 ms 29384 KB Output is correct
17 Correct 336 ms 29340 KB Output is correct
18 Correct 330 ms 29380 KB Output is correct
19 Correct 364 ms 30200 KB Output is correct
20 Correct 425 ms 30492 KB Output is correct
21 Correct 354 ms 29992 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 3 ms 5028 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 5040 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 4 ms 5032 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 5036 KB Output is correct
12 Correct 3 ms 5032 KB Output is correct
13 Correct 3 ms 4996 KB Output is correct
14 Correct 3 ms 5012 KB Output is correct
15 Correct 348 ms 29964 KB Output is correct
16 Correct 364 ms 30420 KB Output is correct
17 Correct 430 ms 17732 KB Output is correct
18 Correct 1272 ms 16328 KB Output is correct
19 Correct 1187 ms 16020 KB Output is correct
20 Correct 1182 ms 16104 KB Output is correct
21 Correct 1194 ms 16124 KB Output is correct
22 Correct 1355 ms 16740 KB Output is correct
23 Correct 1303 ms 16416 KB Output is correct
24 Correct 1337 ms 16644 KB Output is correct
25 Correct 882 ms 17500 KB Output is correct
26 Correct 815 ms 17600 KB Output is correct
27 Correct 860 ms 18644 KB Output is correct
28 Correct 793 ms 17460 KB Output is correct
29 Correct 820 ms 17056 KB Output is correct
30 Correct 792 ms 17684 KB Output is correct
31 Correct 821 ms 17056 KB Output is correct
32 Correct 368 ms 30928 KB Output is correct
33 Correct 347 ms 30260 KB Output is correct
34 Correct 344 ms 29124 KB Output is correct
35 Correct 333 ms 28992 KB Output is correct
36 Correct 412 ms 31984 KB Output is correct
37 Correct 395 ms 31472 KB Output is correct
38 Correct 437 ms 32388 KB Output is correct
39 Correct 359 ms 31140 KB Output is correct
40 Correct 393 ms 30888 KB Output is correct
41 Correct 332 ms 30400 KB Output is correct
42 Correct 340 ms 29508 KB Output is correct
43 Correct 398 ms 33044 KB Output is correct
44 Correct 422 ms 32908 KB Output is correct
45 Correct 399 ms 31960 KB Output is correct
46 Correct 330 ms 30404 KB Output is correct
47 Correct 346 ms 29384 KB Output is correct
48 Correct 336 ms 29340 KB Output is correct
49 Correct 330 ms 29380 KB Output is correct
50 Correct 364 ms 30200 KB Output is correct
51 Correct 425 ms 30492 KB Output is correct
52 Correct 354 ms 29992 KB Output is correct
53 Correct 1298 ms 15144 KB Output is correct
54 Correct 1534 ms 15480 KB Output is correct
55 Correct 1611 ms 15892 KB Output is correct
56 Correct 1518 ms 16088 KB Output is correct
57 Correct 1526 ms 16744 KB Output is correct
58 Correct 1438 ms 15268 KB Output is correct
59 Correct 1617 ms 17924 KB Output is correct
60 Correct 1482 ms 15760 KB Output is correct
61 Correct 1283 ms 14796 KB Output is correct
62 Correct 1355 ms 16208 KB Output is correct
63 Correct 1612 ms 15820 KB Output is correct
64 Correct 1323 ms 17352 KB Output is correct
65 Correct 1673 ms 15692 KB Output is correct
66 Correct 1667 ms 16452 KB Output is correct
67 Correct 1598 ms 16148 KB Output is correct
68 Correct 1994 ms 19176 KB Output is correct
69 Correct 484 ms 30532 KB Output is correct
70 Correct 491 ms 29312 KB Output is correct
71 Correct 504 ms 32512 KB Output is correct
72 Correct 534 ms 17152 KB Output is correct
73 Correct 379 ms 17968 KB Output is correct
74 Correct 453 ms 19732 KB Output is correct
75 Correct 994 ms 17984 KB Output is correct
76 Correct 1114 ms 18456 KB Output is correct
77 Correct 1079 ms 17896 KB Output is correct
78 Correct 876 ms 18584 KB Output is correct