oj.uz

Submission #916004

# Submission time Handle Problem Language Result Execution time Memory
916004 2024-01-25T06:02:52 Z Juanchoki Regions (IOI09_regions) C++14
19 / 100
 8000 ms 26520 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[200001];
int region[200001];
vector<int> zona[25001];
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);
	
	while (q--)
	{
		cin >> a >> r;
		int resp = 0;
		for (int pos: zona[a])
			for (int i = ini[pos]+1; i < fin[pos]; i++)
				if (region[euler[i]] == r) resp++;
		cout << resp/2 << endl;
	}
	
}

Subtask #1
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7768 KB Output is correct
2 Correct 2 ms 7768 KB Output is correct
3 Correct 3 ms 7768 KB Output is correct
4 Correct 4 ms 7768 KB Output is correct
5 Correct 9 ms 7768 KB Output is correct
6 Correct 14 ms 7768 KB Output is correct
7 Correct 18 ms 7768 KB Output is correct
8 Correct 26 ms 7768 KB Output is correct
9 Correct 314 ms 8416 KB Output is correct
10 Correct 68 ms 8460 KB Output is correct
11 Correct 293 ms 8728 KB Output is correct
12 Correct 1431 ms 9096 KB Output is correct
13 Correct 126 ms 8888 KB Output is correct
14 Correct 679 ms 9788 KB Output is correct
15 Execution timed out 8074 ms 12028 KB Time limit exceeded

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8038 ms 12476 KB Time limit exceeded
2 Execution timed out 8068 ms 11200 KB Time limit exceeded
3 Execution timed out 8025 ms 13984 KB Time limit exceeded
4 Correct 2394 ms 9352 KB Output is correct
5 Execution timed out 8032 ms 11184 KB Time limit exceeded
6 Execution timed out 8061 ms 10492 KB Time limit exceeded
7 Execution timed out 8013 ms 11644 KB Time limit exceeded
8 Execution timed out 8051 ms 16240 KB Time limit exceeded
9 Execution timed out 8048 ms 16472 KB Time limit exceeded
10 Execution timed out 8010 ms 21036 KB Time limit exceeded
11 Execution timed out 8077 ms 15336 KB Time limit exceeded
12 Execution timed out 8077 ms 17328 KB Time limit exceeded
13 Execution timed out 8034 ms 17532 KB Time limit exceeded
14 Execution timed out 8013 ms 16972 KB Time limit exceeded
15 Execution timed out 8064 ms 21304 KB Time limit exceeded
16 Execution timed out 8096 ms 26520 KB Time limit exceeded
17 Execution timed out 8007 ms 25324 KB Time limit exceeded