QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#125853#5502. Dazzling MountainHaciyevWA 274ms35032kbC++141.5kb2023-07-17 19:41:582023-07-17 19:42:03

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-17 19:42:03]
  • 评测
  • 测评结果:WA
  • 用时:274ms
  • 内存:35032kb
  • [2023-07-17 19:41:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
#define pb push_back
#define oo 1000000000000000LL
#define ff first
#define ss second
const int mx=1000001;
vector<int> g[mx];
int used[mx],n,sub[mx],out[mx],leaf[mx];
void dfs(int u) {
    used[u]=1;
    sub[u]=1;
    for(int i=0;i<int(g[u].size());++i) {
        int v=g[u][i];
        if(!used[v]) {
            dfs(v);
            sub[u]+=sub[v];
            leaf[u]+=leaf[v];
        }
    }
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int t; cin>>t;
    while(t--) {
        cin >> n;
        int k=0;
        for(int i=0;i<=n;++i) {
            sub[i]=used[i]=leaf[i]=out[i]=0;
            g[i].clear();
        }
        for(int i=1;i<n;++i) {
            int u,v; cin>>u>>v;
            g[u].pb(v),g[v].pb(u);
            out[u]++;
        }
        for(int i=1;i<=n;++i) {
            if(!out[i]) {
                leaf[i]=1; ++k;
            }
        }
        dfs(1);
        vector<int>ans;
        int check[n+2];
        memset(check,0,sizeof(check));
        for(int i=1;i<=n;++i) {
            check[sub[i]]+=leaf[i];
        }
        for(int i=1;i<=n;++i) {
            if(check[i]==k) {
                ans.pb(i);
            }
        }
        cout << int(ans.size()) << "\n";
        for(int i=0;i<int(ans.size());++i) {
            cout << ans[i] << " ";
        }
        cout << "\n";
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 35032kb

input:

1
9
1 2
2 3
3 4
3 5
2 6
6 7
7 8
7 9

output:

4
1 3 8 9 

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 274ms
memory: 34056kb

input:

10000
906
675 189
555 889
491 97
791 419
175 694
713 842
788 513
159 354
670 815
652 546
253 87
89 278
563 429
522 900
202 657
331 865
35 605
735 532
612 471
657 386
7 886
856 164
224 777
73 534
481 631
711 698
240 465
115 181
191 825
311 155
709 501
207 849
294 546
591 682
96 405
210 696
861 13
781...

output:

1
906 
2
5 11 
1
111 
3
436 437 438 
1
181 
1
142 
1
436 
2
56 57 
4
124 125 126 127 
1
12 
1
19 
1
67 
2
147 148 
1
69 
2
219 220 
2
61 62 
4
305 306 307 308 
1
309 
2
23 24 
2
300 301 
2
3 5 
1
303 
1
48 
1
68 
1
142 
2
245 246 
1
608 
1
1005 
1
67 
1
18 
1
125 
1
297 
1
4 
1
160 
5
188 189 190 19...

result:

wrong answer 1st lines differ - expected: '63', found: '1'