Submission #494678

#TimeUsernameProblemLanguageResultExecution timeMemory
494678avaneeshk098Birokracija (COCI18_birokracija)C++17
50 / 100
1074 ms23224 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...