QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#310171 | #8134. LCA Counting | ucup-team992# | WA | 1ms | 5592kb | C++17 | 2.5kb | 2024-01-21 06:28:13 | 2024-01-21 06:28:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define F first
#define S second
typedef int uci;
#define int long long
int diff[200001];
int has[200001];
bool leaf[200001];
int lc;
void pre(int v, vector<vector<int>> &adj){
if(leaf[v]){
has[v] = 1;
return;
}
for(int i : adj[v]){
pre(i, adj);
has[v] += has[i];
}
}
void recurse(int v, vector<int> &ins, vector<vector<int>> &adj){
int ones = adj[v].size();
ones -= 2;
vector<pair<vector<int>, int>> comp(adj[v].size());
for(int i{}; i < adj[v].size(); ++i){
recurse(adj[v][i], comp[i].F, adj);
comp[i].S = has[adj[v][i]];
}
sort(comp.begin(), comp.end());
int run{};
int c{};
for(int i{}; i < adj[v].size(); ++i){
if(comp[i].F.empty())
continue;
if(c < ones){
for(int j : comp[i].F)
ins.push_back(j+run);
ins.push_back(run+comp[i].S);
c++;
}else{
for(int j : comp[i].F)
ins.push_back(j+run);
}
run += comp[i].S;
}
for(int i{}; i < adj[v].size(); ++i){
if(comp[i].F.size())
continue;
if(c < ones){
for(int j : comp[i].F)
ins.push_back(j+run);
ins.push_back(run+comp[i].S);
c++;
}else{
for(int j : comp[i].F)
ins.push_back(j+run);
}
run += comp[i].S;
}
/*
cout << "vertex: " << v << '\n';
for(int i : ins)
cout << i << ' ';
cout << '\n';
*/
}
void solve(){
memset(has, 0, sizeof(has));
int n;
cin >> n;
vector<vector<int>> adj(n);
vector<int> par(n);
for(int i{1}; i < n; ++i){
cin >> par[i];
par[i]--;
adj[par[i]].push_back(i);
}
memset(leaf, 0, sizeof(leaf));
int tot = n;
lc = 0;
for(int i{}; i < n; ++i){
if(adj[i].empty()){
leaf[i] = true;
lc++;
}
if(adj[i].size() == 1)
tot--;
}
pre(0, adj);
for(int i{}; i < n; ++i)
diff[i] = 2;
vector<int> ones;
recurse(0, ones, adj);
for(int i : ones){
diff[lc-i] = 1;
}
vector<int> out(lc, tot);
for(int i = lc-1; i >= 0; --i){
out[i] = tot;
tot -= diff[i];
}
for(int i : out)
cout << i << ' ';
cout << '\n';
}
uci main(){
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5340kb
input:
7 1 1 2 4 2 2
output:
1 3 5 6
result:
ok 4 number(s): "1 3 5 6"
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 5592kb
input:
10 1 1 2 2 1 1 1 2 4
output:
1 3 4 5 6 8 9
result:
wrong answer 3rd numbers differ - expected: '5', found: '4'