oj.uz

Submission #536836

# Submission time Handle Problem Language Result Execution time Memory
536836 2022-03-14T05:45:44 Z phathnv Parkovi (COCI22_parkovi) C++11
30 / 110
 3000 ms 36904 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

int n, k;
long long dist[N];
array<int, 2> par[N];
vector<array<int, 2>> adj[N];
vector<int> ord;
bool mark[N];

void Dfs1(int u, int p) {
    for (auto [v, c] : adj[u]) {
        if (v == p) {
            continue;
        }
        dist[v] = dist[u] + c;
        par[v] = {u, c};
        Dfs1(v, u);
    }
}

void Dfs2(int u, long long rem) {
    if (mark[u] || rem < 0) {
        return;
    }
    mark[u] = true;
    for (auto [v, c] : adj[u]) {
        Dfs2(v, rem - c);
    }
}

vector<int> calc(long long r) {
    fill(mark + 1, mark + 1 + n, false);
    vector<int> res;
    for (auto u : ord) {
        if (mark[u]) {
            continue;
        }
        long long rem = r;
        while (par[u][0] && rem >= par[u][1]) {
            rem -= par[u][1];
            u = par[u][0];
        }
        res.push_back(u);
        Dfs2(u, r);
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i < n; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }
    Dfs1(1, -1);
    ord.resize(n);
    iota(ord.begin(), ord.end(), 1);
    sort(ord.begin(), ord.end(), [&](int u, int v){
            return dist[u] > dist[v];
         });
    long long l = 0, r = 1e15, ans = -1;
    while (l <= r) {
        long long mid = (l + r) >> 1;
        int cnt = calc(mid).size();
        if (cnt <= k) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << '\n';
    vector<int> tmp = calc(ans);
    fill(mark + 1, mark + 1 + n, false);
    for (auto u : tmp) {
        mark[u] = true;
    }
    for (int i = 1; i <= n; ++i) {
        if (!mark[i] && (int)tmp.size() < k) {
            tmp.push_back(i);
        }
    }
    sort(tmp.begin(), tmp.end());
    for (int x : tmp) {
        cout << x << ' ';
    }
    cout << '\n';
    return 0;
}

Compilation message

Main.cpp: In function 'void Dfs1(int, int)':
Main.cpp:14:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |     for (auto [v, c] : adj[u]) {
      |               ^
Main.cpp: In function 'void Dfs2(int, long long int)':
Main.cpp:29:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |     for (auto [v, c] : adj[u]) {
      |               ^

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 32148 KB Output is correct
2 Correct 211 ms 34308 KB Output is correct
3 Correct 290 ms 21480 KB Output is correct
4 Correct 951 ms 20556 KB Output is correct
5 Correct 923 ms 20192 KB Output is correct
6 Correct 1076 ms 19528 KB Output is correct
7 Correct 1063 ms 19008 KB Output is correct
8 Correct 1153 ms 19472 KB Output is correct
9 Correct 1022 ms 19420 KB Output is correct
10 Correct 1060 ms 19912 KB Output is correct
11 Correct 881 ms 21324 KB Output is correct
12 Correct 2856 ms 21812 KB Output is correct
13 Correct 1626 ms 22680 KB Output is correct
14 Execution timed out 3088 ms 20176 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 34804 KB Output is correct
2 Correct 183 ms 33996 KB Output is correct
3 Correct 176 ms 32552 KB Output is correct
4 Correct 194 ms 32392 KB Output is correct
5 Correct 221 ms 36456 KB Output is correct
6 Correct 236 ms 35340 KB Output is correct
7 Correct 236 ms 36508 KB Output is correct
8 Correct 190 ms 34376 KB Output is correct
9 Correct 183 ms 34088 KB Output is correct
10 Correct 188 ms 33472 KB Output is correct
11 Correct 212 ms 32432 KB Output is correct
12 Correct 247 ms 36904 KB Output is correct
13 Correct 240 ms 36876 KB Output is correct
14 Correct 235 ms 35388 KB Output is correct
15 Correct 214 ms 32800 KB Output is correct
16 Correct 196 ms 31596 KB Output is correct
17 Correct 206 ms 31464 KB Output is correct
18 Correct 238 ms 32936 KB Output is correct
19 Correct 235 ms 34272 KB Output is correct
20 Correct 240 ms 34740 KB Output is correct
21 Correct 233 ms 33688 KB Output is correct

Subtask #4
0 / 60.0

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