QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#235959 | #5502. Dazzling Mountain | froxyy | WA | 7ms | 75580kb | C++20 | 2.2kb | 2023-11-03 14:10:09 | 2023-11-03 14:10:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define ssize(x) int(x.size())
#define pb push_back
#define fi first
#define se second
#define ld long double
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ld, ld> pd;
using LL=long long;
#ifdef DEBUG
auto &operator<<(auto &o, pair<auto, auto> p) {
return o << "()" << p.first << ", " << p.second <<")";
}
auto operator<<(auto &o, auto x)-> decltype(x.end(), o) {
o << "{";int i = 0;
for(auto e : x) o << ", "+!i++<<e;
return o <<"}";
}
#define debug(x...) cerr << "["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(x)
#else
#define debug(...) {}
#endif
const int MAXN = 1e6 + 7;
vector<int> G[MAXN];
int subtree[MAXN];
set<int> s[MAXN];
void init(int n) {
for (int i = 1; i <= n; i++) {
subtree[i] = 0;
s[i].clear();
if(!G[i].empty())
G[i].clear();
}
}
void DFS_subtree(int v, int p) {
subtree[v] = 1;
for (auto u : G[v]) {
if (u != p) {
DFS_subtree(u, v);
subtree[v] += subtree[u];
}
}
}
void DFS(int v, int p) {
bool ok = false;
for (auto u : G[v]) {
if (u == p) continue;
DFS(u, v);
if (!ok) {
ok = true;
s[v] = s[u];
}
else {
for (auto i : s[v]) {
if (s[u].find(i) == s[u].end()) {
s[v].erase(i);
}
}
}
}
s[v].insert(subtree[v]);
}
void solve() {
int n;
cin >> n;
init(n);
for (int i = 0; i < n-1; i++) {
int a, b;
cin >> a >> b;
G[a].pb(b);
G[b].pb(a);
}
DFS_subtree(1, 1);
DFS(1, 1);
for (auto i : s[1]) {
cout << i << ' ' ;
}
cout << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int z;
cin >> z;
while(z--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 7ms
memory: 75580kb
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 '