QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#125853 | #5502. Dazzling Mountain | Haciyev | WA | 274ms | 35032kb | C++14 | 1.5kb | 2023-07-17 19:41:58 | 2023-07-17 19:42:03 |
Judging History
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'