QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#233449 | #5502. Dazzling Mountain | Haciyev | WA | 4ms | 35808kb | C++14 | 1.6kb | 2023-10-31 17:44:59 | 2023-10-31 17:44:59 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//Into Sandy's city
using ll = long long;
using ld = long double;
//using ordered_set = tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>;
#define pb push_back
#define oo 10000000000000000
#define ff first
#define ss second
const int mx=1e6+5;
int n,sub[mx],leaf[mx];
bool used[mx];
vector<int> g[mx];
map<int,int> mp;
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];
}
}
}
void solve() {
mp.clear();
memset(sub,0,sizeof(sub));
memset(leaf,0,sizeof(leaf));
memset(used,false,sizeof(used));
cin >> n;
for(int i=0;i<=n;++i){
g[i].clear();
}
for(int i=1;i<n;++i){
int a,b; cin >> a >> b;
g[a].pb(b),g[b].pb(a);
}
int leaf_cnt=0;
for(int i=2;i<=n;++i){
if(int(g[i].size())==1) {
leaf[i]=1;
++leaf_cnt;
}
}
dfs(1);
for(int i=1;i<=n;++i){
mp[sub[i]]+=leaf[i];
}
for(int i=0;i<=n;++i){
if(mp[i]>=leaf_cnt) {
cout << i << " ";
}
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int z; cin >> z;
while(z--) {
solve();
cout << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 35808kb
input:
1 9 1 2 2 3 3 4 3 5 2 6 6 7 7 8 7 9
output:
1 3 8 9
result:
wrong answer 1st lines differ - expected: '4', found: '1 3 8 9 '