oj.uz

Submission #581678

# Submission time Handle Problem Language Result Execution time Memory
581678 2022-06-23T03:15:06 Z PurpleCrayon Pastiri (COI20_pastiri) C++17
31 / 100
 1000 ms 72648 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) {
    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 169 ms 69620 KB Output is correct
2 Correct 215 ms 70004 KB Output is correct
3 Correct 217 ms 70036 KB Output is correct
4 Correct 265 ms 72648 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12372 KB Output is correct
2 Correct 8 ms 12348 KB Output is correct
3 Correct 411 ms 38640 KB Output is correct
4 Correct 406 ms 40896 KB Output is correct
5 Correct 566 ms 38804 KB Output is correct
6 Execution timed out 1004 ms 41576 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12216 KB Output is correct
2 Correct 8 ms 12116 KB Output is correct
3 Correct 8 ms 12116 KB Output is correct
4 Correct 7 ms 12132 KB Output is correct
5 Correct 8 ms 12212 KB Output is correct
6 Correct 8 ms 12116 KB Output is correct
7 Correct 7 ms 12244 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 7 ms 12220 KB Output is correct
11 Correct 10 ms 12116 KB Output is correct
12 Correct 7 ms 12060 KB Output is correct
13 Correct 10 ms 12116 KB Output is correct
14 Correct 8 ms 12220 KB Output is correct
15 Correct 8 ms 12116 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 39508 KB Output is correct
2 Correct 514 ms 39320 KB Output is correct
3 Correct 562 ms 40088 KB Output is correct
4 Correct 499 ms 38652 KB Output is correct
5 Correct 389 ms 35008 KB Output is correct
6 Correct 528 ms 43856 KB Output is correct
7 Correct 548 ms 42460 KB Output is correct
8 Correct 585 ms 42476 KB Output is correct
9 Correct 722 ms 38800 KB Output is correct
10 Correct 542 ms 38752 KB Output is correct
11 Correct 377 ms 40052 KB Output is correct
12 Correct 349 ms 41600 KB Output is correct
13 Correct 382 ms 42316 KB Output is correct
14 Correct 302 ms 41388 KB Output is correct
15 Correct 64 ms 16844 KB Output is correct
16 Execution timed out 1028 ms 36600 KB Time limit exceeded
17 Halted 0 ms 0 KB -