Submission #237508

#TimeUsernameProblemLanguageResultExecution timeMemory
237508NONAMEBirokracija (COCI18_birokracija)C++17
60 / 100
1100 ms34040 KiB
#include <bits/stdc++.h> #define sz(x) int(x.size()) #define pb push_back #define mp make_pair #define ft first #define sd second using namespace std; typedef long long ll; const int N = 2e5 + 10; ll f[N]; int n, d[N], pr[N]; vector <int> g[N]; set <int> se[N]; void dfs(int v, int pred = -1) { for (int i = 0; i < sz(g[v]); ++i) { int to = g[v][i]; if (to == pred) continue; d[to] = d[v] + 1; dfs(to, v); } se[pr[v]].insert(v); for (int i = 0; i < sz(g[v]); ++i) { int to = g[v][i]; if (to == pred) continue; if (sz(se[pr[v]]) < sz(se[pr[to]])) { while (!se[pr[v]].empty()) { se[pr[to]].insert(*se[pr[v]].begin()); se[pr[v]].erase(se[pr[v]].begin()); } pr[v] = pr[to]; } else { while (!se[pr[to]].empty()) { se[pr[v]].insert(*se[pr[to]].begin()); se[pr[to]].erase(se[pr[to]].begin()); } pr[to] = pr[v]; } } for (set <int> :: iterator it = se[pr[v]].begin(); it != se[pr[v]].end(); ++it) f[v] += d[*it] - d[v] + 1; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i < n; ++i) pr[i] = i; for (int i = 1; i < n; ++i) { int x; cin >> x; x--; g[i].pb(x); g[x].pb(i); } dfs(0); for (int i = 0; i < n; ++i) cout << f[i] << ' '; }
#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...