QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#163754 | #6745. Delete the Tree | ucup-team1209# | WA | 2ms | 3680kb | C++20 | 1.8kb | 2023-09-04 14:48:40 | 2023-09-04 14:48:40 |
Judging History
answer
#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using pi = pair <int, int> ;
cs int N = 505;
int n;
vector <int> e[N];
vector <pi> E;
bool skip[N];
void dfs(int u, int f) {
int d = 1;
bool o = 0;
for(int v : e[u])
if(v != f) {
dfs(v, u);
++ d;
o |= skip[v];
}
if(d == 1) {
skip[u] = 1;
}
else {
if(d == 2 && !o) {
skip[u] = 1;
int a = e[u][0], b = e[u][1];
E.pb({a, b});
}
}
for(int v : e[u])
if(v != f) {
if(!skip[u] && !skip[v]) {
E.pb({u, v});
}
}
}
int main() {
#ifdef zqj
freopen("1.in","r",stdin);
#endif
cin >> n;
for(int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
e[u].pb(v), e[v].pb(u);
}
vector <int> p(n);
for(int i = 0; i < n; i++) p[i] = i + 1;
while(p.size()) {
if(p.size() == 1) {
cout << 1 << ' ' << p[0] << '\n';
break;
}
E.clear();
int rt = p[0];
for(int x : p) if(e[x].size() > 1) rt = x;
dfs(rt, 0);
for(int i = 1; i <= n; i++) e[i].clear();
for(auto [x, y] : E) {
e[x].pb(y);
e[y].pb(x);
}
vector <int> np, ans;
for(int x : p)
if(!skip[x]) np.pb(x);
else ans.pb(x);
p = np;
// for(auto x : p) cout << x << ' '; cout <<endl;
// for(auto [x, y] : E) cout << x << ' ' << y << endl;
// cout << p.size() << ' ' << E.size() << endl;
if(p.size() ) assert(p.size() - 1 == E.size());
cout << ans.size() << ' ';
for(int x : ans) cout << x << ' ';
cout << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3680kb
input:
5 1 2 1 3 1 4 4 5
output:
3 2 3 5 1 4 1 1
result:
wrong answer