답안 #916004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916004	2024-01-25T06:02:52 Z	Juanchoki	Regions (IOI09_regions)	C++14	19 / 100	8000 ms	26520 KB

regions

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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