oj.uz

Submission #583833

# Submission time Handle Problem Language Result Execution time Memory
583833 2022-06-26T09:30:58 Z eecs Pastiri (COI20_pastiri) C++17
100 / 100
 551 ms 68564 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 154 ms 62796 KB Output is correct
2 Correct 197 ms 62796 KB Output is correct
3 Correct 231 ms 62796 KB Output is correct
4 Correct 225 ms 68564 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14264 KB Output is correct
2 Correct 12 ms 14164 KB Output is correct
3 Correct 386 ms 38740 KB Output is correct
4 Correct 373 ms 41120 KB Output is correct
5 Correct 496 ms 38296 KB Output is correct
6 Correct 526 ms 40596 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 9 ms 14116 KB Output is correct
3 Correct 11 ms 14032 KB Output is correct
4 Correct 8 ms 14076 KB Output is correct
5 Correct 9 ms 14036 KB Output is correct
6 Correct 8 ms 14036 KB Output is correct
7 Correct 7 ms 14036 KB Output is correct
8 Correct 8 ms 14040 KB Output is correct
9 Correct 8 ms 14012 KB Output is correct
10 Correct 8 ms 14008 KB Output is correct
11 Correct 9 ms 14064 KB Output is correct
12 Correct 8 ms 13988 KB Output is correct
13 Correct 9 ms 14000 KB Output is correct
14 Correct 8 ms 14164 KB Output is correct
15 Correct 11 ms 14132 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 39212 KB Output is correct
2 Correct 503 ms 38988 KB Output is correct
3 Correct 529 ms 41808 KB Output is correct
4 Correct 547 ms 38208 KB Output is correct
5 Correct 412 ms 37076 KB Output is correct
6 Correct 455 ms 45288 KB Output is correct
7 Correct 493 ms 44004 KB Output is correct
8 Correct 488 ms 43636 KB Output is correct
9 Correct 532 ms 38316 KB Output is correct
10 Correct 551 ms 38372 KB Output is correct
11 Correct 375 ms 40372 KB Output is correct
12 Correct 316 ms 43184 KB Output is correct
13 Correct 370 ms 45044 KB Output is correct
14 Correct 287 ms 41836 KB Output is correct
15 Correct 45 ms 18012 KB Output is correct
16 Correct 475 ms 36568 KB Output is correct
17 Correct 328 ms 37420 KB Output is correct
18 Correct 422 ms 33812 KB Output is correct
19 Correct 481 ms 42956 KB Output is correct
20 Correct 498 ms 45756 KB Output is correct
21 Correct 492 ms 38548 KB Output is correct
22 Correct 468 ms 39000 KB Output is correct