oj.uz

Submission #168316

# Submission time Handle Problem Language Result Execution time Memory
168316 2019-12-12T11:27:05 Z aydinenes Birokracija (COCI18_birokracija) C++11
100 / 100
 294 ms 48184 KB 
#include<bits/stdc++.h>

#define mid(l,r) ((l+r)/2)

using namespace std;

const int N = 1e6 + 7;
const int inf = 1e9 + 7;

int n;

int a[N];

vector<int> g[N];

long long ans[N];

void dfsa(int node, int p){
	ans[node] = 1;
	
	for(int i = 0; i < g[node].size(); i++){
		int x = g[node][i];
		if(x == p)	continue;
		dfsa(x, node);
		ans[node] += ans[x];
	}
}

void dfsb(int node, int p){
	for(int i = 0; i < g[node].size(); i++){
		int x = g[node][i];
		if(x == p)	continue;
		dfsb(x, node);
		ans[node] += ans[x];
	}
}

int main(){
	
	cin >> n;
	
	for(int i = 2; i <= n; i++){
		cin >> a[i];
		g[i].push_back(a[i]);
		g[a[i]].push_back(i);
	}
	
	dfsa(1, 0);
	dfsb(1, 0);
	
	for(int i = 1; i <= n; i++){
		cout << ans[i] << " ";
	}
}

Compilation message

birokracija.cpp: In function 'void dfsa(int, int)':
birokracija.cpp:21:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++){
                 ~~^~~~~~~~~~~~~~~~
birokracija.cpp: In function 'void dfsb(int, int)':
birokracija.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++){
                 ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23800 KB Output is correct
2 Correct 23 ms 23928 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 23 ms 23928 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 24696 KB Output is correct
2 Correct 43 ms 25080 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 27104 KB Output is correct
2 Correct 81 ms 27120 KB Output is correct
3 Correct 81 ms 28384 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 33028 KB Output is correct
2 Correct 193 ms 34796 KB Output is correct
3 Correct 198 ms 48184 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 33208 KB Output is correct
2 Correct 195 ms 33688 KB Output is correct
3 Correct 192 ms 36132 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 32888 KB Output is correct
2 Correct 195 ms 34040 KB Output is correct
3 Correct 190 ms 38520 KB Output is correct