oj.uz

Submission #765006

# Submission time Handle Problem Language Result Execution time Memory
765006 2023-06-24T07:23:13 Z dxz05 Parkovi (COCI22_parkovi) C++17
50 / 110
 3000 ms 78432 KB 
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
#define BIT(x, i) (((x) >> (i)) & 1)
//#define endl '\n'

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 2e5 + 30;

int n;
vector<pair<int, int>> g[N];

ll dep[N];
int up[N][18];
ll sum[N][18];

void dfs0(int v, int p){
    up[v][0] = p;
    sum[v][0] = dep[v] - dep[p];
    for (int i = 1; i < 18; i++){
        int pp = up[v][i - 1];
        up[v][i] = up[pp][i - 1];
        sum[v][i] = sum[v][i - 1] + sum[pp][i - 1];
    }

    for (auto [u, w] : g[v]){
        if (u != p){
            dep[u] = dep[v] + w;
            dfs0(u, v);
        }
    }
}

bool deleted[N];

void dfs(int v, int p, ll dist){
    deleted[v] = true;

    for (auto [u, w] : g[v]){
        if (u == p) continue;
        if (w <= dist){
            dfs(u, v, dist - w);
        } else {
            break;
        }
    }
}

int parks[N];

int parks_cnt(ll d){
    priority_queue<pair<ll, int>> pq;
    for (int i = 1; i <= n; i++) pq.emplace(dep[i], i);
    fill(deleted + 1, deleted + n + 1, false);

    int sz = 0;
    while (!pq.empty()){
        int v = pq.top().second;
        if (deleted[v]){
            pq.pop();
            continue;
        }

        ll x = d;
        for (int i = 17; i >= 0; i--){
            if (sum[v][i] <= x){
                x -= sum[v][i];
                v = up[v][i];
            }
        }

        parks[sz++] = v;

        dfs(v, -1, d);
    }

    return sz;
}

int ans[N];

void solve(){
    int k;
    cin >> n >> k;

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

    int root = 1;
    for (int i = 1; i <= n; i++){
        if (g[i].size() > 1) root = i;

        sort(all(g[i]), [&](auto x, auto y){
            return x.second < y.second;
        });

    }

    dfs0(root, root);

    int sz = 0;

    ll l = 0, r = 2e14;
    while (l <= r){
        ll m = (l + r) >> 1;

        int res = parks_cnt(m);

        if (res <= k){
            sz = res;
            for (int i = 0; i < res; i++) ans[i] = parks[i];
            r = m - 1;
        } else {
            l = m + 1;
        }
    }

    sort(ans, ans + sz);

    cout << ++r << endl;
    for (int i = 0; i < sz; i++) cout << ans[i] << ' ';

    int x = k - sz;
    for (int i = 1; i <= n; i++){
        if (x == 0) break;
        int j = lower_bound(ans, ans + sz, i) - ans;
        if (j == sz || ans[j] != i){
            cout << i << ' ';
            x--;
        }
    }

    cout << endl;
}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
//    cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        // cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

#ifdef LOCAL
    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:153:13: warning: unused variable 'startTime' [-Wunused-variable]
  153 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4980 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 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 4948 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 888 ms 74012 KB Output is correct
2 Correct 910 ms 75684 KB Output is correct
3 Correct 1792 ms 64016 KB Output is correct
4 Correct 2044 ms 60488 KB Output is correct
5 Correct 2007 ms 58636 KB Output is correct
6 Correct 1996 ms 58712 KB Output is correct
7 Correct 2418 ms 59108 KB Output is correct
8 Correct 2380 ms 61780 KB Output is correct
9 Correct 2311 ms 60396 KB Output is correct
10 Correct 2422 ms 61732 KB Output is correct
11 Correct 1880 ms 62924 KB Output is correct
12 Correct 1727 ms 60984 KB Output is correct
13 Correct 1961 ms 65752 KB Output is correct
14 Correct 1724 ms 60468 KB Output is correct
15 Correct 1789 ms 60604 KB Output is correct
16 Correct 1799 ms 61588 KB Output is correct
17 Correct 1855 ms 60596 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 924 ms 76892 KB Output is correct
2 Correct 872 ms 75252 KB Output is correct
3 Correct 859 ms 71636 KB Output is correct
4 Correct 900 ms 71500 KB Output is correct
5 Correct 953 ms 75348 KB Output is correct
6 Correct 1112 ms 75392 KB Output is correct
7 Correct 1101 ms 77556 KB Output is correct
8 Correct 858 ms 77296 KB Output is correct
9 Correct 860 ms 76780 KB Output is correct
10 Correct 862 ms 75344 KB Output is correct
11 Correct 870 ms 72900 KB Output is correct
12 Correct 1063 ms 77608 KB Output is correct
13 Correct 1114 ms 78432 KB Output is correct
14 Correct 1105 ms 77140 KB Output is correct
15 Correct 872 ms 75304 KB Output is correct
16 Correct 840 ms 72572 KB Output is correct
17 Correct 857 ms 72312 KB Output is correct
18 Correct 919 ms 75820 KB Output is correct
19 Correct 887 ms 73364 KB Output is correct
20 Correct 932 ms 75532 KB Output is correct
21 Correct 918 ms 74316 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4980 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 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 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 888 ms 74012 KB Output is correct
16 Correct 910 ms 75684 KB Output is correct
17 Correct 1792 ms 64016 KB Output is correct
18 Correct 2044 ms 60488 KB Output is correct
19 Correct 2007 ms 58636 KB Output is correct
20 Correct 1996 ms 58712 KB Output is correct
21 Correct 2418 ms 59108 KB Output is correct
22 Correct 2380 ms 61780 KB Output is correct
23 Correct 2311 ms 60396 KB Output is correct
24 Correct 2422 ms 61732 KB Output is correct
25 Correct 1880 ms 62924 KB Output is correct
26 Correct 1727 ms 60984 KB Output is correct
27 Correct 1961 ms 65752 KB Output is correct
28 Correct 1724 ms 60468 KB Output is correct
29 Correct 1789 ms 60604 KB Output is correct
30 Correct 1799 ms 61588 KB Output is correct
31 Correct 1855 ms 60596 KB Output is correct
32 Correct 924 ms 76892 KB Output is correct
33 Correct 872 ms 75252 KB Output is correct
34 Correct 859 ms 71636 KB Output is correct
35 Correct 900 ms 71500 KB Output is correct
36 Correct 953 ms 75348 KB Output is correct
37 Correct 1112 ms 75392 KB Output is correct
38 Correct 1101 ms 77556 KB Output is correct
39 Correct 858 ms 77296 KB Output is correct
40 Correct 860 ms 76780 KB Output is correct
41 Correct 862 ms 75344 KB Output is correct
42 Correct 870 ms 72900 KB Output is correct
43 Correct 1063 ms 77608 KB Output is correct
44 Correct 1114 ms 78432 KB Output is correct
45 Correct 1105 ms 77140 KB Output is correct
46 Correct 872 ms 75304 KB Output is correct
47 Correct 840 ms 72572 KB Output is correct
48 Correct 857 ms 72312 KB Output is correct
49 Correct 919 ms 75820 KB Output is correct
50 Correct 887 ms 73364 KB Output is correct
51 Correct 932 ms 75532 KB Output is correct
52 Correct 918 ms 74316 KB Output is correct
53 Execution timed out 3051 ms 59828 KB Time limit exceeded
54 Halted 0 ms 0 KB -