Submission #916002

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
916002	2024-01-25T05:54:15 Z	Juanchoki	Regions (IOI09_regions)	C++14	30 / 100	5226 ms	14524 KB

regions

#include <bits/stdc++.h>
using namespace std;
int mapa[501][501];
vector<int> adj[200001];
int region[200001];
vector<int> zona[501];
vector<int> euler;
int ini[200001], fin[200001], cnt = 0;
void dfs(int nodo)
{
	euler.push_back(nodo);
	ini[nodo] = cnt++;
	for (int v: adj[nodo])
		dfs(v);
	euler.push_back(nodo);
	fin[nodo] = cnt++;
}
int main() 
{
	int n, r, q, a; cin >> n >> r >> q;
	cin >> region[1];
	zona[region[1]].push_back(1);
	for (int i = 2; i <= n; i++)
	{
		cin >> a;
		adj[a].push_back(i);
		cin >> a;
		region[i] = a;
		zona[a].push_back(i);
	}
	dfs(1);
	//for (int x: euler) cout << x << " " << region[x] << '\n';
	for (int i = 1; i <= 500; i++)
	{
		for (int pos: zona[i])
		{
			for (int j = ini[pos]+1; j < fin[pos]; j++)
			{
				mapa[i][region[euler[j]]]++;
			}
		}
	}
	while (q--)
	{
		cin >> a >> r;
		cout << mapa[a][r]/2 << endl;
	}
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	7256 KB	Output is correct
2	Correct	2 ms	7256 KB	Output is correct
3	Correct	2 ms	7256 KB	Output is correct
4	Correct	5 ms	7256 KB	Output is correct
5	Correct	5 ms	7344 KB	Output is correct
6	Correct	12 ms	7768 KB	Output is correct
7	Correct	14 ms	7512 KB	Output is correct
8	Correct	16 ms	7768 KB	Output is correct
9	Correct	46 ms	8432 KB	Output is correct
10	Correct	48 ms	8712 KB	Output is correct
11	Correct	65 ms	8536 KB	Output is correct
12	Correct	143 ms	9440 KB	Output is correct
13	Correct	72 ms	8792 KB	Output is correct
14	Correct	84 ms	9144 KB	Output is correct
15	Correct	1810 ms	11760 KB	Output is correct

Subtask #2

15.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1667 ms	12208 KB	Output is correct
2	Correct	728 ms	10700 KB	Output is correct
3	Correct	5226 ms	13760 KB	Output is correct
4	Runtime error	7 ms	14524 KB	Execution killed with signal 11
5	Runtime error	7 ms	14424 KB	Execution killed with signal 11
6	Runtime error	7 ms	14424 KB	Execution killed with signal 11
7	Runtime error	9 ms	14512 KB	Execution killed with signal 11
8	Runtime error	7 ms	14424 KB	Execution killed with signal 11
9	Runtime error	7 ms	14424 KB	Execution killed with signal 11
10	Runtime error	8 ms	14424 KB	Execution killed with signal 11
11	Runtime error	9 ms	14492 KB	Execution killed with signal 11
12	Runtime error	8 ms	14424 KB	Execution killed with signal 11
13	Runtime error	9 ms	14424 KB	Execution killed with signal 11
14	Runtime error	10 ms	14424 KB	Execution killed with signal 11
15	Runtime error	8 ms	14424 KB	Execution killed with signal 11
16	Runtime error	7 ms	14424 KB	Execution killed with signal 11
17	Runtime error	7 ms	14424 KB	Execution killed with signal 11