# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
467352 | 2021-08-22T17:51:58 Z | phathnv | Pastiri (COI20_pastiri) | C++17 | 665 ms | 60536 KB |
#include <bits/stdc++.h> using namespace std; const int N = 500007; int n, k, sheep[N], h[N], d[N], trace[N], numNode; pair<int, int> best[2 * N]; vector<int> adj[N], child[2 * N]; bool vst[N]; int main() { scanf("%d %d", &n, &k); for (int i = 1; i < n; i++) { int u, v; scanf("%d %d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); } for (int i = 1; i <= k; i++) scanf("%d", &sheep[i]); queue<int> qu; h[1] = 1; qu.push(1); while (!qu.empty()) { int u = qu.front(); qu.pop(); for (int v : adj[u]) if (!h[v]) { h[v] = h[u] + 1; qu.push(v); } } for (int i = 1; i <= k; i++) { int x = sheep[i]; ++numNode; trace[x] = numNode; d[x] = 1; qu.push(x); } while (!qu.empty()) { int u = qu.front(); qu.pop(); for (int v : adj[u]) { if (!d[v]) { trace[v] = trace[u]; d[v] = d[u] + 1; qu.push(v); } else if (d[v] == d[u] + 1) { int newNode = ++numNode; child[newNode].push_back(trace[u]); child[newNode].push_back(trace[v]); trace[v] = newNode; } } } for (int u = 1; u <= numNode; u++) { if (u <= k) best[u] = {h[u], 0}; else best[u] = {1e9, 0}; for (int v : child[u]) { best[u] = min(best[u], best[v]); vst[v] = true; } best[u].second = u; } for (int u = 1; u <= numNode; u++) if (vst[u]) { best[u] = {1e9, 1e9}; vst[u] = false; } for (int u = numNode; u >= 1; u--) { for (int v : child[u]) best[v] = min(best[v], best[u]); } vector<int> ord(k); iota(ord.begin(), ord.end(), 1); sort(ord.begin(), ord.end(), [&](const int &a, const int &b){ return h[sheep[a]] > h[sheep[b]]; }); map<int, int> nodeToVex; for (int i = 1; i <= n; i++) nodeToVex[trace[i]] = i; vector<int> answer; for (int x : ord) { if (vst[x]) continue; queue<int> qu; qu.push(best[x].second); answer.push_back(nodeToVex[best[x].second]); while (!qu.empty()) { int u = qu.front(); qu.pop(); if (vst[u]) continue; vst[u] = true; for (int v : child[u]) qu.push(v); } } printf("%d\n", answer.size()); for (int x : answer) printf("%d ", x); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 216 ms | 57000 KB | Output is correct |
2 | Incorrect | 259 ms | 57048 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 35652 KB | Output is correct |
2 | Correct | 21 ms | 35780 KB | Output is correct |
3 | Correct | 504 ms | 57680 KB | Output is correct |
4 | Correct | 527 ms | 60536 KB | Output is correct |
5 | Incorrect | 619 ms | 57020 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 21 ms | 35660 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 665 ms | 58688 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |