oj.uz

Submission #788738

# Submission time Handle Problem Language Result Execution time Memory
788738 2023-07-20T14:40:05 Z hafo Parkovi (COCI22_parkovi) C++14
110 / 110
 938 ms 35288 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e18 + 69;

int n, k, u, v, w, cnt = 0;
vector<pa> g[maxn];
bool placed[maxn];
ll dist[maxn], reach[maxn];

void dfs(int u, int par, ll lim) {
    dist[u] = oo;
    reach[u] = 0;

    for(auto e:g[u]) {
        int v = e.fi, w = e.se;
        if(v == par) continue;
        dfs(v, u, lim);

        if(reach[v] + min(1LL * w, dist[v]) <= lim) {
            placed[v] = 0;
            if(reach[v] + dist[v] > lim) {
                maxi(reach[u], reach[v] + w);
            }
            mini(dist[u], dist[v] + w);
        } else {
            placed[v] = 1;
            cnt++;
            mini(dist[u], w);
        }
    } 
}

bool check(ll lim) {
    cnt = 0;
    dfs(1, 0, lim);
    if(reach[1] + dist[1] <= lim) placed[1] = 0;
    else {
        placed[1] = 1;
        cnt++;
    }
    return cnt <= k;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

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

    ll l = 0, r = 1e15, mid, res;
    while(l <= r) {
        mid = l + r >> 1;
        if(check(mid)) {
            res = mid;
            r = mid - 1;
        } else l = mid + 1;
    }

    cout<<res<<"\n";
    vector<int> ans;
    check(res);
    for(int i = 1; i <= n; i++) 
        if(placed[i]) ans.pb(i);
    for(int i = 1; i <= n; i++) 
        if(Size(ans) < k && !placed[i]) ans.pb(i);
    for(auto i:ans) cout<<i<<" ";
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:77:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |         mid = l + r >> 1;
      |               ~~^~~
Main.cpp:86:10: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |     check(res);
      |     ~~~~~^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 5024 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 5020 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 31480 KB Output is correct
2 Correct 282 ms 33604 KB Output is correct
3 Correct 339 ms 20492 KB Output is correct
4 Correct 690 ms 19372 KB Output is correct
5 Correct 661 ms 18820 KB Output is correct
6 Correct 730 ms 18840 KB Output is correct
7 Correct 709 ms 17652 KB Output is correct
8 Correct 659 ms 18324 KB Output is correct
9 Correct 664 ms 18780 KB Output is correct
10 Correct 706 ms 19012 KB Output is correct
11 Correct 573 ms 20488 KB Output is correct
12 Correct 666 ms 20432 KB Output is correct
13 Correct 557 ms 21872 KB Output is correct
14 Correct 553 ms 18968 KB Output is correct
15 Correct 646 ms 18572 KB Output is correct
16 Correct 634 ms 19956 KB Output is correct
17 Correct 544 ms 19252 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 34124 KB Output is correct
2 Correct 292 ms 33308 KB Output is correct
3 Correct 277 ms 31828 KB Output is correct
4 Correct 250 ms 31780 KB Output is correct
5 Correct 279 ms 34816 KB Output is correct
6 Correct 335 ms 34140 KB Output is correct
7 Correct 315 ms 35288 KB Output is correct
8 Correct 283 ms 33624 KB Output is correct
9 Correct 271 ms 33316 KB Output is correct
10 Correct 270 ms 32800 KB Output is correct
11 Correct 243 ms 31768 KB Output is correct
12 Correct 340 ms 35200 KB Output is correct
13 Correct 347 ms 35152 KB Output is correct
14 Correct 299 ms 34272 KB Output is correct
15 Correct 285 ms 32060 KB Output is correct
16 Correct 243 ms 30932 KB Output is correct
17 Correct 270 ms 30924 KB Output is correct
18 Correct 256 ms 32272 KB Output is correct
19 Correct 310 ms 32712 KB Output is correct
20 Correct 273 ms 33220 KB Output is correct
21 Correct 272 ms 32400 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 5024 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 5020 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 275 ms 31480 KB Output is correct
16 Correct 282 ms 33604 KB Output is correct
17 Correct 339 ms 20492 KB Output is correct
18 Correct 690 ms 19372 KB Output is correct
19 Correct 661 ms 18820 KB Output is correct
20 Correct 730 ms 18840 KB Output is correct
21 Correct 709 ms 17652 KB Output is correct
22 Correct 659 ms 18324 KB Output is correct
23 Correct 664 ms 18780 KB Output is correct
24 Correct 706 ms 19012 KB Output is correct
25 Correct 573 ms 20488 KB Output is correct
26 Correct 666 ms 20432 KB Output is correct
27 Correct 557 ms 21872 KB Output is correct
28 Correct 553 ms 18968 KB Output is correct
29 Correct 646 ms 18572 KB Output is correct
30 Correct 634 ms 19956 KB Output is correct
31 Correct 544 ms 19252 KB Output is correct
32 Correct 299 ms 34124 KB Output is correct
33 Correct 292 ms 33308 KB Output is correct
34 Correct 277 ms 31828 KB Output is correct
35 Correct 250 ms 31780 KB Output is correct
36 Correct 279 ms 34816 KB Output is correct
37 Correct 335 ms 34140 KB Output is correct
38 Correct 315 ms 35288 KB Output is correct
39 Correct 283 ms 33624 KB Output is correct
40 Correct 271 ms 33316 KB Output is correct
41 Correct 270 ms 32800 KB Output is correct
42 Correct 243 ms 31768 KB Output is correct
43 Correct 340 ms 35200 KB Output is correct
44 Correct 347 ms 35152 KB Output is correct
45 Correct 299 ms 34272 KB Output is correct
46 Correct 285 ms 32060 KB Output is correct
47 Correct 243 ms 30932 KB Output is correct
48 Correct 270 ms 30924 KB Output is correct
49 Correct 256 ms 32272 KB Output is correct
50 Correct 310 ms 32712 KB Output is correct
51 Correct 273 ms 33220 KB Output is correct
52 Correct 272 ms 32400 KB Output is correct
53 Correct 756 ms 19124 KB Output is correct
54 Correct 727 ms 19596 KB Output is correct
55 Correct 689 ms 20300 KB Output is correct
56 Correct 938 ms 19968 KB Output is correct
57 Correct 907 ms 20616 KB Output is correct
58 Correct 654 ms 19292 KB Output is correct
59 Correct 725 ms 21904 KB Output is correct
60 Correct 642 ms 18756 KB Output is correct
61 Correct 744 ms 17520 KB Output is correct
62 Correct 704 ms 18476 KB Output is correct
63 Correct 744 ms 18812 KB Output is correct
64 Correct 681 ms 19984 KB Output is correct
65 Correct 667 ms 19128 KB Output is correct
66 Correct 730 ms 19608 KB Output is correct
67 Correct 650 ms 18304 KB Output is correct
68 Correct 766 ms 21448 KB Output is correct
69 Correct 282 ms 33448 KB Output is correct
70 Correct 304 ms 31512 KB Output is correct
71 Correct 306 ms 34720 KB Output is correct
72 Correct 227 ms 19648 KB Output is correct
73 Correct 208 ms 18932 KB Output is correct
74 Correct 351 ms 20596 KB Output is correct
75 Correct 507 ms 20836 KB Output is correct
76 Correct 552 ms 20124 KB Output is correct
77 Correct 481 ms 20148 KB Output is correct
78 Correct 518 ms 19892 KB Output is correct