oj.uz

Submission #676456

# Submission time Handle Problem Language Result Execution time Memory
676456 2022-12-31T02:06:43 Z badont Birokracija (COCI18_birokracija) C++17
100 / 100
 69 ms 26800 KB 
#include<bits/stdc++.h>
using namespace std;

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

using LL = long long;
using LD = long double;
using pii = pair<LL,LL>;

#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

//var 
LL T;

void solve() {
	LL n;
	cin >> n;
	vector<LL> p(n);

	vector e(n, vector<LL>());
	FOR (i, n - 1) {
		cin >> p[i];
		p[i]--;
		e[p[i]].pb(i);
	}

	//debug(e);	

	vector<LL> dp(n), sub(n);
	auto dfs = [&](auto dfs, LL g, LL d) -> void {
		sub[g] = 1;;
		for (auto u : e[g]) {
			dfs(dfs,u, d + 1);
			dp[g] += dp[u];
			sub[g] += sub[u];
		}
		dp[g] += sub[g];
	};
	dfs(dfs, 0, 1);
	F0R (i, n)
		cout << dp[i] << " \n"[i == n -1];
}

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);

	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();

	cout.flush();
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1684 KB Output is correct
2 Correct 6 ms 2260 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5440 KB Output is correct
2 Correct 23 ms 5716 KB Output is correct
3 Correct 16 ms 6612 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 14900 KB Output is correct
2 Correct 50 ms 16880 KB Output is correct
3 Correct 48 ms 26800 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 14924 KB Output is correct
2 Correct 53 ms 16076 KB Output is correct
3 Correct 48 ms 17776 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 14652 KB Output is correct
2 Correct 49 ms 16304 KB Output is correct
3 Correct 47 ms 19228 KB Output is correct