Submission #760807

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
760807	2023-06-18T14:13:44 Z	pakapu	Regions (IOI09_regions)	C++17	0 / 100	60 ms	27664 KB

regions

#include <bits/stdc++.h>

using namespace std;

int dfs(int u, int cnt, const vector<vector<int>> &g,
		const vector<int> &r, const int r1, const int r2) {
	int rt = 0;
	if(r[u] == r1) {
		cnt++;
	}
	if(r[u] == r2) {
		rt += cnt;
	}

	for(auto v : g[u]) {
		rt += dfs(v, cnt, g, r, r1, r2);
	}

	return rt;
}

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

	int n, nr, q;
	cin >> n >> nr >> q;

	vector<int> a(n);
	vector<int> r(n);
	vector<vector<int>> g(n);

	cin >> r[0];
	for(int i = 1; i < n; i++) {
		int from;
		cin >> from;
		from--;
		g[from].push_back(i);
		cin >> r[i];
	}

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

		cout << dfs(0, 0, g, r, r1, r2) << '\n';
	}

	return 0;
}

Subtask #1

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1 ms	208 KB	Time limit exceeded (wall clock)
2	Execution timed out	1 ms	208 KB	Time limit exceeded (wall clock)
3	Execution timed out	1 ms	208 KB	Time limit exceeded (wall clock)
4	Execution timed out	1 ms	208 KB	Time limit exceeded (wall clock)
5	Execution timed out	1 ms	336 KB	Time limit exceeded (wall clock)
6	Execution timed out	1 ms	336 KB	Time limit exceeded (wall clock)
7	Execution timed out	1 ms	336 KB	Time limit exceeded (wall clock)
8	Execution timed out	1 ms	336 KB	Time limit exceeded (wall clock)
9	Execution timed out	2 ms	976 KB	Time limit exceeded (wall clock)
10	Execution timed out	2 ms	848 KB	Time limit exceeded (wall clock)
11	Execution timed out	3 ms	1232 KB	Time limit exceeded (wall clock)
12	Execution timed out	4 ms	1872 KB	Time limit exceeded (wall clock)
13	Execution timed out	5 ms	1360 KB	Time limit exceeded (wall clock)
14	Execution timed out	6 ms	2000 KB	Time limit exceeded (wall clock)
15	Execution timed out	8 ms	5840 KB	Time limit exceeded (wall clock)

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	13 ms	5968 KB	Time limit exceeded (wall clock)
2	Execution timed out	20 ms	4432 KB	Time limit exceeded (wall clock)
3	Execution timed out	16 ms	8672 KB	Time limit exceeded (wall clock)
4	Execution timed out	8 ms	2128 KB	Time limit exceeded (wall clock)
5	Execution timed out	7 ms	4560 KB	Time limit exceeded (wall clock)
6	Execution timed out	10 ms	3596 KB	Time limit exceeded (wall clock)
7	Execution timed out	12 ms	4664 KB	Time limit exceeded (wall clock)
8	Execution timed out	27 ms	11860 KB	Time limit exceeded (wall clock)
9	Execution timed out	29 ms	10696 KB	Time limit exceeded (wall clock)
10	Execution timed out	34 ms	17784 KB	Time limit exceeded (wall clock)
11	Execution timed out	41 ms	10312 KB	Time limit exceeded (wall clock)
12	Execution timed out	42 ms	12328 KB	Time limit exceeded (wall clock)
13	Execution timed out	38 ms	13040 KB	Time limit exceeded (wall clock)
14	Execution timed out	60 ms	12232 KB	Time limit exceeded (wall clock)
15	Execution timed out	39 ms	18176 KB	Time limit exceeded (wall clock)
16	Execution timed out	42 ms	27664 KB	Time limit exceeded (wall clock)
17	Execution timed out	40 ms	25672 KB	Time limit exceeded (wall clock)