oj.uz

Submission #889725

# Submission time Handle Problem Language Result Execution time Memory
889725 2023-12-20T06:17:11 Z The_Samurai Parkovi (COCI22_parkovi) C++17
30 / 110
 3000 ms 30720 KB 
// I stand with PALESTINE




//#pragma GCC optimize("Ofast,O3")
//#pragma GCC target("avx,avx2")
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const int N = 2e5 + 5;

vector<vector<pair<int, int>>> g(N);
vector<ll> height(N);
vector<int> par(N);

void dfs(int u) {
    for (auto [v, w]: g[u]) {
        if (par[u] == v) continue;
        par[v] = u;
        height[v] = height[u] + w;
        dfs(v);
    }
}

void solve() {
    int n, 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);
    }
    dfs(1);
    vector<bool> marked, copy;
    vector<pair<ll, int>> vec(n);
    for (int i = 1; i <= n; i++) vec[i - 1] = make_pair(height[i], i);
    sort(vec.rbegin(), vec.rend());
//    for (int i = 1; i <= n; i++) cout << height[i] << ' ';
//    cout << endl;
//    for (int i = 0; i < n; i++) cout << vec[i].second << ' ';
//    cout << endl;
    auto check = [&](ll m) -> bool {
        vector<bool> vis(n + 1);
        marked.assign(n + 1, false);
        int need = 0;
        for (auto [d, u]: vec) {
            if (vis[u]) continue;
            need++;
            int root = u;
            while (root != 1 and height[u] - height[par[root]] <= m) root = par[root];
            queue<tuple<ll, int, int>> q; q.emplace(0, root, 0);
            vis[root] = marked[root] = true;
            while (!q.empty()) {
                auto [d, v, p] = q.front(); q.pop();
                for (auto [vv, w]: g[v]) {
                    if (vv != p and d + w <= m and !vis[vv]) {
                        vis[vv] = true;
                        q.emplace(d + w, vv, v);
                    }
                }
            }
        }
//        cout << m << ' ' << need << ' ' << count(marked.begin(), marked.end(), true) << endl;
        return need <= k;
    };
    ll lx = 0, rx = 1e18, best = -1;
    while (lx <= rx) {
        ll mid = (lx + rx) >> 1;
        if (check(mid)) {
            best = mid;
            copy = marked;
            rx = mid - 1;
        } else {
            lx = mid + 1;
        }
    }
    cout << best << '\n';
    vector<int> ans;
    for (int i = 1; i <= n; i++) if (copy[i]) ans.emplace_back(i);
    for (int i = 1; i <= n; i++) {
        if (!copy[i] and ans.size() < k) ans.emplace_back(i);
    }
    for (int x: ans) cout << x << ' ';

}

int main() {
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int q = 1;
//    cin >> q;
    while (q--) {
        solve();
        cout << '\n';
    }
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:84:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |         if (!copy[i] and ans.size() < k) ans.emplace_back(i);
      |                          ~~~~~~~~~~~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 3 ms 7260 KB Output is correct
4 Correct 3 ms 7260 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7260 KB Output is correct
7 Incorrect 4 ms 7260 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 27984 KB Output is correct
2 Correct 162 ms 28668 KB Output is correct
3 Correct 318 ms 21748 KB Output is correct
4 Correct 582 ms 18652 KB Output is correct
5 Correct 512 ms 18140 KB Output is correct
6 Correct 423 ms 17492 KB Output is correct
7 Correct 428 ms 17644 KB Output is correct
8 Correct 556 ms 18128 KB Output is correct
9 Correct 479 ms 18140 KB Output is correct
10 Correct 473 ms 18008 KB Output is correct
11 Correct 1484 ms 18388 KB Output is correct
12 Correct 1882 ms 18224 KB Output is correct
13 Correct 1421 ms 19412 KB Output is correct
14 Correct 1785 ms 18280 KB Output is correct
15 Execution timed out 3074 ms 17888 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 29052 KB Output is correct
2 Correct 161 ms 28448 KB Output is correct
3 Correct 154 ms 27384 KB Output is correct
4 Correct 155 ms 27216 KB Output is correct
5 Correct 309 ms 29892 KB Output is correct
6 Correct 269 ms 29140 KB Output is correct
7 Correct 296 ms 30156 KB Output is correct
8 Correct 168 ms 29188 KB Output is correct
9 Correct 172 ms 28992 KB Output is correct
10 Correct 168 ms 28496 KB Output is correct
11 Correct 157 ms 27784 KB Output is correct
12 Correct 293 ms 30720 KB Output is correct
13 Correct 283 ms 30668 KB Output is correct
14 Correct 268 ms 29644 KB Output is correct
15 Correct 190 ms 28496 KB Output is correct
16 Correct 169 ms 27472 KB Output is correct
17 Correct 169 ms 27588 KB Output is correct
18 Correct 179 ms 28712 KB Output is correct
19 Correct 204 ms 29380 KB Output is correct
20 Correct 204 ms 29648 KB Output is correct
21 Correct 204 ms 28876 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 3 ms 7260 KB Output is correct
4 Correct 3 ms 7260 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7260 KB Output is correct
7 Incorrect 4 ms 7260 KB Output isn't correct
8 Halted 0 ms 0 KB -