oj.uz

Submission #581679

# Submission time Handle Problem Language Result Execution time Memory
581679 2022-06-23T03:15:44 Z PurpleCrayon Pastiri (COI20_pastiri) C++17
100 / 100
 673 ms 71712 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 5e5+10, MOD = 1e9+7;

int n, k, a[N], depth[N], d[N], par[N];
vector<int> adj[N];
bool mark[N];

void dfs(int c, int p) {
    par[c] = p;
    for (auto nxt : adj[c]) if (nxt != p) {
        depth[nxt] = depth[c] + 1;
        dfs(nxt, c);
    }
}
void mark_node(int c) {
    if (mark[c]) return;

    mark[c] = 1;
    for (auto nxt : adj[c]) if (d[nxt] == d[c] - 1)
        mark_node(nxt);
}
void solve() {
    cin >> n >> k;
    for (int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b, --a, --b;
        adj[a].push_back(b), adj[b].push_back(a);
    }
    dfs(0, -1);
    std::fill(d, d + n, MOD);
    vector<int> q; q.reserve(n);
    for (int i = 0; i < k; i++) {
        int c; cin >> c, --c;
        a[i] = c;
        d[c] = 0; q.push_back(c);
    }

    for (int rep = 0; rep < sz(q); rep++) {
        int c = q[rep];
        for (auto nxt : adj[c]) if (d[nxt] > d[c] + 1) {
            d[nxt] = d[c] + 1;
            q.push_back(nxt);
        }
    }

    sort(a, a + n, [&](int x, int y) { return depth[x] > depth[y]; });

    int ans = 0;
    vector<int> pr; pr.reserve(n);
    for (int i = 0; i < k; i++) if (!mark[a[i]]) {
        int use = a[i];
        while (par[use] != -1 && d[par[use]] == depth[a[i]] - depth[par[use]]) {
            use = par[use];
        }
        pr.push_back(use);
        ans++;
        mark_node(use);
    }
    cout << ans << '\n';
    for (int x : pr) cout << x+1 << ' ';
    cout << '\n';
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 68840 KB Output is correct
2 Correct 205 ms 69268 KB Output is correct
3 Correct 222 ms 69276 KB Output is correct
4 Correct 273 ms 71712 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12304 KB Output is correct
2 Correct 8 ms 12244 KB Output is correct
3 Correct 452 ms 37828 KB Output is correct
4 Correct 441 ms 40144 KB Output is correct
5 Correct 505 ms 38092 KB Output is correct
6 Correct 633 ms 40728 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 7 ms 12200 KB Output is correct
4 Correct 8 ms 12144 KB Output is correct
5 Correct 7 ms 12120 KB Output is correct
6 Correct 7 ms 12116 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 8 ms 12116 KB Output is correct
9 Correct 7 ms 12216 KB Output is correct
10 Correct 7 ms 12088 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 8 ms 12144 KB Output is correct
13 Correct 7 ms 12116 KB Output is correct
14 Correct 9 ms 12204 KB Output is correct
15 Correct 8 ms 12116 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 38728 KB Output is correct
2 Correct 521 ms 38588 KB Output is correct
3 Correct 507 ms 39252 KB Output is correct
4 Correct 528 ms 38004 KB Output is correct
5 Correct 413 ms 34340 KB Output is correct
6 Correct 517 ms 42964 KB Output is correct
7 Correct 583 ms 41696 KB Output is correct
8 Correct 566 ms 41800 KB Output is correct
9 Correct 673 ms 38204 KB Output is correct
10 Correct 520 ms 38108 KB Output is correct
11 Correct 352 ms 39248 KB Output is correct
12 Correct 317 ms 40768 KB Output is correct
13 Correct 356 ms 41512 KB Output is correct
14 Correct 296 ms 40848 KB Output is correct
15 Correct 48 ms 16356 KB Output is correct
16 Correct 621 ms 36072 KB Output is correct
17 Correct 373 ms 35488 KB Output is correct
18 Correct 529 ms 34008 KB Output is correct
19 Correct 568 ms 43464 KB Output is correct
20 Correct 546 ms 47576 KB Output is correct
21 Correct 490 ms 38856 KB Output is correct
22 Correct 490 ms 39592 KB Output is correct