oj.uz

Submission #83138

# Submission time Handle Problem Language Result Execution time Memory
83138 2018-11-05T14:19:01 Z Leonardo_Paes Birokracija (COCI18_birokracija) C++11
70 / 100
 1000 ms 11408 KB 
#include <bits/stdc++.h>

using namespace std;

#define MAXN 200100

vector<int> grafo[MAXN];

int resp[MAXN], pai[MAXN], mark[MAXN];

void dfs (int u, int num, int sum){
	mark[u]=1;
	resp[u]+=sum;
	if(pai[u]==0)return;

	if(mark[pai[u]]==0){
		num++;
	}

	dfs(pai[u], num, (sum+num));

}

int main(){

	int n;

	cin >> n;

	for(int i=2; i<=n; i++){

		int p;

		cin >> p;

		grafo[p].push_back(i);
		
		pai[i]=p;
	}

	pai[1]=0;

	for(int i=2; i<=n; i++){
		if(grafo[i].size() == 0){
			dfs(i, 1, 1);
		}
	}

	for(int i=1; i<=n; i++){
		cout << resp[i] << " ";
	}

	cout << endl;

	return 0;

}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5116 KB Output is correct
2 Correct 7 ms 5136 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5136 KB Output is correct
2 Correct 8 ms 5212 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5908 KB Output is correct
2 Correct 78 ms 6164 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 7384 KB Output is correct
2 Correct 430 ms 7816 KB Output is correct
3 Correct 951 ms 7896 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 11408 KB Output is correct
2 Execution timed out 1063 ms 11408 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 11408 KB Output is correct
2 Execution timed out 1066 ms 11408 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 11408 KB Output is correct
2 Execution timed out 1071 ms 11408 KB Time limit exceeded
3 Halted 0 ms 0 KB -