oj.uz

Submission #764981

# Submission time Handle Problem Language Result Execution time Memory
764981 2023-06-24T07:10:28 Z dxz05 Parkovi (COCI22_parkovi) C++17
50 / 110
 3000 ms 76788 KB 
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("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;
        }
    }
}

vector<int> parks(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);

    vector<int> ans;
    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];
            }
        }

        ans.push_back(v);
        dfs(v, -1, d);
    }

    return ans;
}

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);

    vector<int> ans;

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

        vector<int> p = parks(m);

        if (p.size() <= k){
            ans = p;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }


    cout << ++r << endl;
    for (int x : ans) cout << x << ' ';

    int x = k - (int) ans.size();
    for (int i = 1; i <= n; i++){
        if (x == 0) break;
        int j = lower_bound(all(ans), i) - ans.begin();
        if (j == ans.size() || 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 'void solve()':
Main.cpp:120:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  120 |         if (p.size() <= k){
      |             ~~~~~~~~~^~~~
Main.cpp:136:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         if (j == ans.size() || ans[j] != i){
      |             ~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:146:13: warning: unused variable 'startTime' [-Wunused-variable]
  146 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4952 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 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 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 2 ms 4948 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1018 ms 71100 KB Output is correct
2 Correct 1041 ms 72964 KB Output is correct
3 Correct 2017 ms 64092 KB Output is correct
4 Correct 2237 ms 60500 KB Output is correct
5 Correct 2051 ms 58992 KB Output is correct
6 Correct 1926 ms 58952 KB Output is correct
7 Correct 2350 ms 59392 KB Output is correct
8 Correct 2398 ms 62036 KB Output is correct
9 Correct 2398 ms 60616 KB Output is correct
10 Correct 2660 ms 61864 KB Output is correct
11 Correct 1997 ms 62736 KB Output is correct
12 Correct 1765 ms 60740 KB Output is correct
13 Correct 2095 ms 65428 KB Output is correct
14 Correct 1837 ms 60328 KB Output is correct
15 Correct 1843 ms 60396 KB Output is correct
16 Correct 1898 ms 61376 KB Output is correct
17 Correct 1987 ms 60464 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1032 ms 73884 KB Output is correct
2 Correct 935 ms 72304 KB Output is correct
3 Correct 930 ms 68864 KB Output is correct
4 Correct 950 ms 68924 KB Output is correct
5 Correct 950 ms 74484 KB Output is correct
6 Correct 1174 ms 73172 KB Output is correct
7 Correct 1138 ms 75236 KB Output is correct
8 Correct 965 ms 74540 KB Output is correct
9 Correct 989 ms 73908 KB Output is correct
10 Correct 950 ms 72644 KB Output is correct
11 Correct 978 ms 70300 KB Output is correct
12 Correct 1138 ms 76788 KB Output is correct
13 Correct 1152 ms 75996 KB Output is correct
14 Correct 1137 ms 74468 KB Output is correct
15 Correct 977 ms 72636 KB Output is correct
16 Correct 945 ms 70096 KB Output is correct
17 Correct 936 ms 69556 KB Output is correct
18 Correct 1083 ms 72804 KB Output is correct
19 Correct 967 ms 71056 KB Output is correct
20 Correct 1073 ms 72680 KB Output is correct
21 Correct 1002 ms 71564 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4952 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 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 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 2 ms 4948 KB Output is correct
15 Correct 1018 ms 71100 KB Output is correct
16 Correct 1041 ms 72964 KB Output is correct
17 Correct 2017 ms 64092 KB Output is correct
18 Correct 2237 ms 60500 KB Output is correct
19 Correct 2051 ms 58992 KB Output is correct
20 Correct 1926 ms 58952 KB Output is correct
21 Correct 2350 ms 59392 KB Output is correct
22 Correct 2398 ms 62036 KB Output is correct
23 Correct 2398 ms 60616 KB Output is correct
24 Correct 2660 ms 61864 KB Output is correct
25 Correct 1997 ms 62736 KB Output is correct
26 Correct 1765 ms 60740 KB Output is correct
27 Correct 2095 ms 65428 KB Output is correct
28 Correct 1837 ms 60328 KB Output is correct
29 Correct 1843 ms 60396 KB Output is correct
30 Correct 1898 ms 61376 KB Output is correct
31 Correct 1987 ms 60464 KB Output is correct
32 Correct 1032 ms 73884 KB Output is correct
33 Correct 935 ms 72304 KB Output is correct
34 Correct 930 ms 68864 KB Output is correct
35 Correct 950 ms 68924 KB Output is correct
36 Correct 950 ms 74484 KB Output is correct
37 Correct 1174 ms 73172 KB Output is correct
38 Correct 1138 ms 75236 KB Output is correct
39 Correct 965 ms 74540 KB Output is correct
40 Correct 989 ms 73908 KB Output is correct
41 Correct 950 ms 72644 KB Output is correct
42 Correct 978 ms 70300 KB Output is correct
43 Correct 1138 ms 76788 KB Output is correct
44 Correct 1152 ms 75996 KB Output is correct
45 Correct 1137 ms 74468 KB Output is correct
46 Correct 977 ms 72636 KB Output is correct
47 Correct 945 ms 70096 KB Output is correct
48 Correct 936 ms 69556 KB Output is correct
49 Correct 1083 ms 72804 KB Output is correct
50 Correct 967 ms 71056 KB Output is correct
51 Correct 1073 ms 72680 KB Output is correct
52 Correct 1002 ms 71564 KB Output is correct
53 Execution timed out 3066 ms 59860 KB Time limit exceeded
54 Halted 0 ms 0 KB -