Submission #113164

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
113164	2019-05-24T03:49:45 Z	joseacaz	Regions (IOI09_regions)	C++17	0 / 100	8000 ms	121444 KB

regions

#include <iostream>
#include <vector>
#define MAXN 200005
#define MAXR 25005

using namespace std;
typedef long long lld;

lld N, R, Q, region[MAXN], supervisor[MAXN], c, answer[505][MAXR], a, b;
vector < lld > Graph[MAXN];

void dfs ( lld reg, lld node )
{
	answer[reg][region[node]] += c;

	if ( region[node] == reg )
		c++;
	for ( auto i : Graph[node] )
		dfs ( reg, i );
	if ( region[node] == reg )
		c--;
}

int main ()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> R >> Q;
	cin >> region[1];
	for ( lld i = 2; i <= N; i++ )
	{
		cin >> supervisor[i] >> region[i];
		Graph[supervisor[i]].push_back ( i );
	}

	for ( lld i = 1; i <= 500; i++ )
		c = 0, dfs ( i, 1 );

	for ( lld i = 0; i < Q; i++ )
	{
		cin >> a >> b;
		if ( a <= 500 )
			cout << answer[a][b] << "\n";
		else
			cout << "0\n";
		fflush ( stdout );
	}
	return 0;
}

Subtask #1

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	6 ms	7168 KB	Time limit exceeded (wall clock)
2	Execution timed out	7 ms	7168 KB	Time limit exceeded (wall clock)
3	Execution timed out	7 ms	7296 KB	Time limit exceeded (wall clock)
4	Execution timed out	16 ms	7344 KB	Time limit exceeded (wall clock)
5	Execution timed out	9 ms	7424 KB	Time limit exceeded (wall clock)
6	Execution timed out	11 ms	8320 KB	Time limit exceeded (wall clock)
7	Execution timed out	13 ms	7808 KB	Time limit exceeded (wall clock)
8	Execution timed out	19 ms	8192 KB	Time limit exceeded (wall clock)
9	Execution timed out	36 ms	8824 KB	Time limit exceeded (wall clock)
10	Execution timed out	135 ms	9208 KB	Time limit exceeded (wall clock)
11	Execution timed out	215 ms	9020 KB	Time limit exceeded (wall clock)
12	Execution timed out	243 ms	10112 KB	Time limit exceeded (wall clock)
13	Execution timed out	332 ms	9388 KB	Time limit exceeded (wall clock)
14	Execution timed out	550 ms	9380 KB	Time limit exceeded (wall clock)
15	Execution timed out	218 ms	11896 KB	Time limit exceeded (wall clock)

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	866 ms	12248 KB	Time limit exceeded (wall clock)
2	Execution timed out	984 ms	11260 KB	Time limit exceeded (wall clock)
3	Execution timed out	680 ms	14200 KB	Time limit exceeded (wall clock)
4	Execution timed out	424 ms	24184 KB	Time limit exceeded (wall clock)
5	Execution timed out	245 ms	29560 KB	Time limit exceeded (wall clock)
6	Execution timed out	742 ms	36984 KB	Time limit exceeded (wall clock)
7	Execution timed out	1336 ms	49528 KB	Time limit exceeded (wall clock)
8	Execution timed out	711 ms	54136 KB	Time limit exceeded (wall clock)
9	Execution timed out	5724 ms	73508 KB	Time limit exceeded (wall clock)
10	Execution timed out	2174 ms	115248 KB	Time limit exceeded (wall clock)
11	Execution timed out	7373 ms	110352 KB	Time limit exceeded (wall clock)
12	Execution timed out	8025 ms	40248 KB	Time limit exceeded
13	Execution timed out	7660 ms	79320 KB	Time limit exceeded (wall clock)
14	Execution timed out	8055 ms	54588 KB	Time limit exceeded
15	Execution timed out	6007 ms	115652 KB	Time limit exceeded (wall clock)
16	Execution timed out	2224 ms	121444 KB	Time limit exceeded (wall clock)
17	Execution timed out	1812 ms	102668 KB	Time limit exceeded (wall clock)