QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387255#6745. Delete the TreeLackofgodWA 0ms3572kbC++142.1kb2024-04-12 11:08:452024-04-12 11:08:46

Judging History

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

  • [2024-04-12 11:08:46]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3572kb
  • [2024-04-12 11:08:45]
  • 提交

answer

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <map>
#include <bitset>
#include <stack>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <queue>
#define forn(i,aa,bb) for(int i=aa;i<=bb;++i)
#define LL long long 
using namespace std;
const int N=500+5;
const LL mod=998244353;
const int MAXX=1e9;
int n;
vector<int> ed[N];
int sub[N];
int fa[N];
bool vis[N];
vector<int> ed1[N];
queue<int> q;
bool vis1[N];
void dfs1(int x){
    vis[x]=1;
    sub[x]=1;
    for(int y:ed[x]) {
        if (vis[y] || vis1[y]) continue;
        fa[y]=x;
        dfs1(y);
        sub[x]+=sub[y];
    }
}
int minm;
void dfs(int x,int &id,int sum){
    sub[x]=1;
    int maxm=0;
    for(int y:ed[x]) {
        if (y==fa[x] || vis1[y]) continue;
        fa[y]=x;
        dfs(y,id,sum);
        sub[x]+=sub[y];
        maxm=max(maxm,sub[y]);
    } 
    maxm=max(maxm,sum-sub[x]);
    if (maxm<=minm) minm=maxm,id=x;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    //cin>>T;
    T=1;
    while (T--) {
        cin>>n;
        forn(i,1,n-1) {
            int x,y;
            cin>>x>>y;
            ed[x].push_back(y);
            ed[y].push_back(x);
        }
        int root,num=0;
        q.push(1);
        sub[1]=n;
        while (!q.empty()) {
            int cnt=q.size();
            num++;
            while (cnt) {
                minm=MAXX;
                int k=q.front(); q.pop();
                dfs(k,root,sub[k]);
                dfs1(root);
                ed1[num].push_back(root);
                vis1[root]=1;
                for(int y:ed[root]) {
                    if (vis1[y]) continue;
                    q.push(y); 
                }
                cnt--;
            }
            forn(i,1,n)
                vis[i]=0;
        }
        cout<<num<<'\n';
        for(int i=num;i>=1;--i) {
            for(int x:ed1[i]) 
                cout<<x<<' ';
            if (i>1) cout<<'\n';   
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3572kb

input:

5
1 2
1 3
1 4
4 5

output:

3
5 
2 3 4 
1 

result:

wrong output format Unexpected end of file - int32 expected