| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 732177 | 2023-04-28T14:59:20 Z | Redhood | Pastiri (COI20_pastiri) | C++14 | 549 ms | 83224 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#ifdef DEBUG
void __dbg(int x) {cout << x;}
void __dbg(bool x) {cout << x;}
void __dbg(ll x) {cout << x;}
void __dbg(auto x) {
int f = 0;
for (int i : x)
cout << (f++ ? ", " : ""), __dbg(i);
}
void _dbg() {
cout << "]\e[39m" << endl;
}
template<typename T, typename... V>
void _dbg(T t, V... v) {
__dbg(t);
if (sizeof...(v))
cout << ", ";
_dbg(v...);
}
#define debug(x...) do {cout << "\e[92m" << __func__ << ":" << __LINE__ << "\t[" << #x << "] = ["; _dbg(x); } while (false)
#else
#define debug(...) 42
#endif
void mini(auto &a, auto b) {a = min(a, b); }
void maxi(auto &a, auto b) {a = max(a, b); }
int n, k;
vector<vi> G;
vi dists, tribes, comp;
const int NOT = -1;
const int TOL = -2;
int dfs(int i, int p) {
bool tolight = (dists[i] == 0);
bool lightchild = false;
int bestcomp = -1; // 0 = można tylko tutaj
for (int j : G[i]) if (j != p) {
int x = dfs(j, i);
if (x >= 0 && dists[j] == 1 + dists[i])
maxi(bestcomp, x);
if (x == TOL) {
if (dists[j] + 1 == dists[i]) {
lightchild = true;
}
else if (dists[j] == 1 + dists[i]) {
comp[j] = true;
maxi(bestcomp, dists[j] - 1);
}
else
comp[j] = true;
}
}
debug(i, dists[i], bestcomp, tolight, lightchild);
if (bestcomp >= 0)
tolight = false;
if (bestcomp >= 1)
lightchild = false;
if (p == -1 && (tolight || lightchild))
comp[i] = true;
if (tolight || lightchild)
return TOL;
if (bestcomp >= 1)
return bestcomp - 1;
return NOT;
}
void solve() {
cin >> n >> k;
G.assign(n, vi());
dists.assign(n, -1);
comp.assign(n, 0);
tribes.resize(k);
rep(_, n-1) {
int u, v;
cin >> u >> v;
--u; --v;
G[u].push_back(v);
G[v].push_back(u);
}
deque<int> bfs;
rep(i, k) {
cin >> tribes[i];
--tribes[i];
dists[tribes[i]] = 0;
bfs.push_back(tribes[i]);
}
while (sz(bfs)) {
int x = bfs[0];
bfs.pop_front();
for (int i : G[x]) {
if (dists[i] != -1)
continue;
dists[i] = dists[x] + 1;
bfs.push_back(i);
}
}
debug(tribes);
debug(dists);
dfs(0, -1);
int cc = accumulate(all(comp), 0);
cout << cc << '\n';
rep(i, n) if (comp[i])
cout << i+1 << ' ';
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int z = 1;
// cin >> z;
while (z--)
solve();
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 167 ms | 77312 KB | Output is correct |
| 2 | Correct | 196 ms | 77352 KB | Output is correct |
| 3 | Correct | 217 ms | 77396 KB | Output is correct |
| 4 | Correct | 253 ms | 83224 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 596 KB | Output is correct |
| 2 | Correct | 2 ms | 596 KB | Output is correct |
| 3 | Correct | 428 ms | 38900 KB | Output is correct |
| 4 | Correct | 422 ms | 41164 KB | Output is correct |
| 5 | Correct | 549 ms | 38224 KB | Output is correct |
| 6 | Correct | 518 ms | 41804 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 340 KB | Output is correct |
| 2 | Correct | 1 ms | 440 KB | Output is correct |
| 3 | Correct | 1 ms | 468 KB | Output is correct |
| 4 | Correct | 1 ms | 340 KB | Output is correct |
| 5 | Correct | 1 ms | 468 KB | Output is correct |
| 6 | Correct | 1 ms | 468 KB | Output is correct |
| 7 | Correct | 2 ms | 468 KB | Output is correct |
| 8 | Correct | 1 ms | 432 KB | Output is correct |
| 9 | Correct | 1 ms | 468 KB | Output is correct |
| 10 | Correct | 1 ms | 468 KB | Output is correct |
| 11 | Correct | 1 ms | 340 KB | Output is correct |
| 12 | Correct | 1 ms | 340 KB | Output is correct |
| 13 | Correct | 1 ms | 456 KB | Output is correct |
| 14 | Correct | 1 ms | 468 KB | Output is correct |
| 15 | Correct | 1 ms | 468 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 473 ms | 39456 KB | Output is correct |
| 2 | Correct | 468 ms | 39192 KB | Output is correct |
| 3 | Correct | 477 ms | 42160 KB | Output is correct |
| 4 | Correct | 510 ms | 38284 KB | Output is correct |
| 5 | Correct | 352 ms | 34720 KB | Output is correct |
| 6 | Correct | 465 ms | 47896 KB | Output is correct |
| 7 | Correct | 453 ms | 45372 KB | Output is correct |
| 8 | Correct | 488 ms | 44828 KB | Output is correct |
| 9 | Correct | 488 ms | 38348 KB | Output is correct |
| 10 | Correct | 513 ms | 38472 KB | Output is correct |
| 11 | Correct | 373 ms | 40336 KB | Output is correct |
| 12 | Correct | 347 ms | 44268 KB | Output is correct |
| 13 | Correct | 383 ms | 46120 KB | Output is correct |
| 14 | Correct | 289 ms | 42028 KB | Output is correct |
| 15 | Correct | 49 ms | 6748 KB | Output is correct |
| 16 | Correct | 492 ms | 35536 KB | Output is correct |
| 17 | Correct | 370 ms | 35032 KB | Output is correct |
| 18 | Correct | 393 ms | 31444 KB | Output is correct |
| 19 | Correct | 476 ms | 45284 KB | Output is correct |
| 20 | Correct | 505 ms | 49892 KB | Output is correct |
| 21 | Correct | 462 ms | 38488 KB | Output is correct |
| 22 | Correct | 465 ms | 39184 KB | Output is correct |