oj.uz

Submission #583837

# Submission time Handle Problem Language Result Execution time Memory
583837 2022-06-26T09:38:15 Z eecs Pastiri (COI20_pastiri) C++17
100 / 100
 552 ms 60044 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 500010;
int n, K, d[maxn], mx[maxn];
vector<int> G[maxn];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> K;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);
    }
    memset(d, -1, sizeof(d));
    queue<int> Q;
    while (K--) {
        int x;
        cin >> x;
        Q.push(x), d[x] = 0;
    }
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int v : G[u]) if (!~d[v]) {
            Q.push(v), d[v] = d[u] + 1;
        }
    }
    vector<int> res;
    auto dfs = [&](auto self, int u, int fa) -> bool {
        mx[u] = -1;
        bool flag = !d[u];
        for (int v : G[u]) if (v ^ fa) {
            flag |= self(self, v, u);
            mx[u] = max(mx[u], mx[v] - 1);
        }
        if (flag && mx[u] == d[u]) flag = 0;
        if (flag && d[fa] <= d[u]) res.push_back(u), mx[u] = d[u], flag = 0;
        return flag;
    };
    dfs(dfs, 1, 0);
    cout << res.size() << "\n";
    for (int x : res) cout << x << " ";
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 56108 KB Output is correct
2 Correct 190 ms 56104 KB Output is correct
3 Correct 193 ms 56140 KB Output is correct
4 Correct 244 ms 60044 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14164 KB Output is correct
2 Correct 10 ms 14164 KB Output is correct
3 Correct 395 ms 32172 KB Output is correct
4 Correct 392 ms 34412 KB Output is correct
5 Correct 536 ms 31704 KB Output is correct
6 Correct 542 ms 33868 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14036 KB Output is correct
2 Correct 8 ms 14036 KB Output is correct
3 Correct 8 ms 14036 KB Output is correct
4 Correct 10 ms 13984 KB Output is correct
5 Correct 11 ms 14036 KB Output is correct
6 Correct 9 ms 14036 KB Output is correct
7 Correct 8 ms 14036 KB Output is correct
8 Correct 8 ms 14036 KB Output is correct
9 Correct 9 ms 14076 KB Output is correct
10 Correct 8 ms 14036 KB Output is correct
11 Correct 8 ms 13980 KB Output is correct
12 Correct 8 ms 14036 KB Output is correct
13 Correct 8 ms 14036 KB Output is correct
14 Correct 8 ms 14036 KB Output is correct
15 Correct 9 ms 14036 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 32424 KB Output is correct
2 Correct 476 ms 32256 KB Output is correct
3 Correct 455 ms 33892 KB Output is correct
4 Correct 552 ms 31692 KB Output is correct
5 Correct 356 ms 30520 KB Output is correct
6 Correct 486 ms 36756 KB Output is correct
7 Correct 460 ms 35792 KB Output is correct
8 Correct 505 ms 35744 KB Output is correct
9 Correct 544 ms 31704 KB Output is correct
10 Correct 540 ms 31672 KB Output is correct
11 Correct 372 ms 33612 KB Output is correct
12 Correct 280 ms 35264 KB Output is correct
13 Correct 335 ms 36300 KB Output is correct
14 Correct 287 ms 35208 KB Output is correct
15 Correct 44 ms 16932 KB Output is correct
16 Correct 487 ms 30332 KB Output is correct
17 Correct 286 ms 30780 KB Output is correct
18 Correct 407 ms 28484 KB Output is correct
19 Correct 528 ms 35772 KB Output is correct
20 Correct 517 ms 38792 KB Output is correct
21 Correct 482 ms 31900 KB Output is correct
22 Correct 503 ms 32260 KB Output is correct