QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#163754#6745. Delete the Treeucup-team1209#WA 2ms3680kbC++201.8kb2023-09-04 14:48:402023-09-04 14:48:40

Judging History

你现在查看的是最新测评结果

  • [2023-09-04 14:48:40]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3680kb
  • [2023-09-04 14:48:40]
  • 提交

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