#include <bits/stdc++.h>
#pragma GCC optimize "trapv"
#define ff first
#define int long long int
#define ss second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define vi vector<int>
#define mii map<int,int>
#define pqb priority_queue<int>
#define max_size 100000000
#define pqs priority_queue<int,vi,greater<int> >
#define setbits(x) __builtin_popcountll(x)
#define mod (int)1e9+7
#define w(t) int t; cin >> t; while(t--)
#define inf 1e18
//#define ps(x,y) fixed<<setprecision(y)<<x
#define mk(arr,n,type) type *arr=new type[n];
#define range(a,b) substr(a,b-a+1)
#define mina(a,b,c) min(a, min(b, c))
#define maxa(a,b,c) max(a, max(b, c))
#define sz(a) (int)a.size()
#define endl '\n'
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl;
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define FOR(x,y) for(int i = x; i < y; i++)
#define rrep(a,b,x,y) for(int x = 0; x < a; x++) for(int y = 0; y < b; y++)
#define rrep1(a,b,x,y) for(int x = 1; x <= a; x++) for(int y = 0; y <= b; y++)
#define rrepo(a,b,x,y) for(int x = 0; x < a; x++){ for(int y = 0; y < b; y++)
#define rrepo1(a,b,x,y) for(int x = 1; x <= a; x++){ for(int y = 0; y <= b; y++)
using namespace std;
bool sortbysecond(const pair<int,int> &a, const pair<int,int> &b){ return (a.second < b.second); }
int64_t ceil_div(int64_t a, int64_t b) {if(a%b != 0){ return ((a/b)+1);} else{ return (a/b);}}
double max(double a, double b){ if(a >= b){ return a; } else{ return b; } }
double min(double a, double b){if(a <= b){return a;} else{return b; }}
bool modd(double a, double b){if(floor(a/b) == ceil(a/b)){return true;} return false;}
bool stringsort(const string &a, const string &b){return a.length() > b.length();}
bool specsort(const pair<long double,int> &a, const pair<long double,int> &b){
return a.first - a.second > b.first - b.second;
}
struct ufds{
vi link, siz;
int cmp;
ufds(int n) : link(n), siz(n,1) { iota(link.begin(), link.end(), 0); cmp = n;}
int find(int x){
if(x == link[x]) return x;
return link[x] = find(link[x]);
}
bool same(int x, int y){
return find(x) == find(y);
}
bool unite(int x, int y){
x = find(x);
y = find(y);
if(x == y) return false;
if(x < y) swap(x,y);
siz[x] += siz[y];
link[y] = x;
cmp--;
return true;
}
int components(){
return cmp;
}
bool size(int x){
return siz[link[x]];
}
};
struct segtree{
vi a;
vector<pii> seg;
int siz;
segtree(int n, vi &b) : seg(4*n) { a = b; }
pii combine(pii c, pii b){
if(c.first < b.first) return c;
else if(c.first > b.first) return b;
return {c.first, c.second + b.second};
}
void build(int l, int r, int pos){
if(l == r){ // if l == r it means it is a laef node so only 1 minimum
seg[pos].first = a[l];
seg[pos].second = 1;
return;
}
int mid = (l+r)/2;
build(l,mid, pos*2); // filling left tree for minimum
build(mid+1, r, pos*2+1); // filling right tree for minimum
seg[pos] = combine(seg[pos*2], seg[pos*2+1]);
}
pii query(int l, int r, int ql, int qr, int pos){
if(l > qr || r < ql) return {inf, inf};
if(l >= ql && r <= qr) return seg[pos];
int mid = (l+r)/2;
pii q1 = query(l, mid, ql, qr, pos*2);
pii q2 = query(mid+1, r, ql, qr, pos*2 + 1);
int val = min(q1.first, q2.first);
if(q1.first == q2.first){
return {val, q1.second + q2.second};
}
else if(val == q1.first){
return {val, q1.second};
}
else if(val == q2.first){
return {val, q2.second};
}
}
void update(int l, int r, int p, int x, int pos){
if(l == r){
seg[pos].first = x;
seg[pos].second = 1;
return;
}
int mid = (l+r)/2;
if(p <= mid){
update(l, mid, p, x, pos*2);
}
else{
update(mid+1, r, p , x, pos*2 + 1);
}
seg[pos] = combine(seg[pos*2], seg[pos*2+1]);
}
};
int child;
int level = 1;
void dfs(int u, vi &visited, vector<set<int>> &adj, vi &score){
visited[u] = 1;
int next = inf;
for(auto v : adj[u]) next = min(next, v);
if(next != inf && !visited[next]){
dfs(next, visited, adj, score);
adj[u].erase(child);
level++;
score[u] += level;
}
if(next == inf){
score[u]++;
child = u;
level = 1;
return;
}
}
void solve(){
int n;
cin >> n;
vector<set<int>> adj(n+1);
for(int i = 2; i <= n; i++){
int k;
cin >> k;
adj[k].insert(i);
}
vi visited(n+1);
vi score(n+1);
while((int)adj[1].size() != 0){
dfs(1, visited, adj, score);
for(int i = 0; i < n; i++) visited[i] = 0;
}
dfs(1, visited, adj, score);
for(auto i : score){
if(i != 0) cout << i << " ";
}
cout << endl;
}
int32_t main(){
FIO;
//w(t){solve();}
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
372 KB |
Output is correct |
| 2 |
Correct |
3 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
6 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
364 KB |
Output is correct |
| 2 |
Correct |
9 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1071 ms |
2512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1066 ms |
8364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1032 ms |
23208 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
23224 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1062 ms |
22724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
