Submission #116142

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
116142	2019-06-10T20:47:32 Z	luciocf	Regions (IOI09_regions)	C++14	30 / 100	1254 ms	53624 KB

regions

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5+10;
const int maxr = 510;

typedef long long ll;

int n, R, q;
int region[maxn];

ll ans[maxr][maxr];

vector<int> grafo[maxn];

int dfs(int u, int p, int r)
{
	int qtd = 0;
	if (region[u] == r)
		qtd = 1;

	for (auto v: grafo[u])
	{
		if (v == p) continue;

		qtd += dfs(v, u, r);
	}

	ans[region[u]][r] += 1ll*qtd;
	return qtd;
}

int main(void)
{
	cin >> n >> R >> q;

	cin >> region[1];
	for (int i = 2; i <= n; i++)
	{
		int p;
		cin >> p >> region[i];

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

	for (int i = 1; i <= R; i++)
		dfs(1, 0, i);

	for (int i = 1; i <= q; i++)
	{
		int r1, r2;
		cin >> r1 >> r2;

		cout << ans[r1][r2] << endl;
	}
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	5020 KB	Output is correct
2	Correct	6 ms	4992 KB	Output is correct
3	Correct	8 ms	5040 KB	Output is correct
4	Correct	10 ms	5120 KB	Output is correct
5	Correct	15 ms	5248 KB	Output is correct
6	Correct	23 ms	6144 KB	Output is correct
7	Correct	39 ms	5760 KB	Output is correct
8	Correct	27 ms	5888 KB	Output is correct
9	Correct	64 ms	6704 KB	Output is correct
10	Correct	176 ms	7200 KB	Output is correct
11	Correct	227 ms	6668 KB	Output is correct
12	Correct	454 ms	7800 KB	Output is correct
13	Correct	388 ms	7248 KB	Output is correct
14	Correct	384 ms	6896 KB	Output is correct
15	Correct	311 ms	10408 KB	Output is correct

Subtask #2

15.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1161 ms	9724 KB	Output is correct
2	Correct	1088 ms	9080 KB	Output is correct
3	Correct	1254 ms	11952 KB	Output is correct
4	Runtime error	31 ms	11936 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	36 ms	12456 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	48 ms	13560 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	59 ms	14760 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	84 ms	18100 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	118 ms	20508 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	132 ms	22140 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	157 ms	24480 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	144 ms	23248 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Runtime error	147 ms	23336 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Runtime error	169 ms	23920 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	164 ms	26556 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	186 ms	53624 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Runtime error	189 ms	23976 KB	Execution killed with signal 11 (could be triggered by violating memory limits)