oj.uz

Submission #583836

# Submission time Handle Problem Language Result Execution time Memory
583836 2022-06-26T09:37:38 Z eecs Pastiri (COI20_pastiri) C++17
0 / 100
 523 ms 55064 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[u] == d[fa]) res.push_back(u), mx[u] = d[u], flag = 0;
        return flag;
    };
    if (dfs(dfs, 1, 0)) res.push_back(1);
    cout << res.size() << "\n";
    for (int x : res) cout << x << " ";
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 55044 KB Output is correct
2 Incorrect 209 ms 55064 KB Sheep 2503 not protected
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14176 KB Sheep 856 not protected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14036 KB Sheep 9 not protected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 523 ms 32384 KB Sheep 54 not protected
2 Halted 0 ms 0 KB -