Submission #162770

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
162770	2019-11-09T16:46:50 Z	faremy	Regions (IOI09_regions)	C++14	34 / 100	1620 ms	131076 KB

regions

#include <iostream>
#include <algorithm>
#include <vector>


const int MAXN = 2e5;
const int MAXR = 25e3;
const int SQRTN = 2;

std::vector<int> tree[MAXN];
int color[MAXN];

int ofColor[MAXR];
int dfsPre[MAXN], dfsPost[MAXN];

int order[MAXR], revOrder[MAXR];
int ofNewColor[MAXR];

long long onOfColor[MAXR];
std::vector<long long> ancestersOfColor[MAXR];
std::vector<int> intervalStarts[MAXR];
std::vector<int> intervalEnds[MAXR];


int analysetree(int node, int seen)
{
	ofColor[color[node]]++;
	dfsPre[node] = seen;

	int subseen = 1;
	for (int child : tree[node])
		subseen += analysetree(child, seen + subseen);
	dfsPost[node] = seen + subseen;
	return (subseen + 1);
}

void recolor(int colors, int nodes)
{
	for (int iColor = 0; iColor < colors; iColor++)
		order[iColor] = iColor;
	std::sort(order, order + colors, [](int a, int b) { return (ofColor[a] > ofColor[b]); });

	for (int iColor = 0; iColor < colors; iColor++)
		ofNewColor[iColor] = ofColor[order[iColor]];
	for (int iColor = 0; iColor < colors; iColor++)
		ofColor[iColor] = ofNewColor[iColor];

	for (int iColor = 0; iColor < colors; iColor++)
		revOrder[order[iColor]] = iColor;
	for (int iNode = 0; iNode < nodes; iNode++)
		color[iNode] = revOrder[color[iNode]];
}

void buildpartialanswers(int node, int colors, int bigColors)
{
	if (color[node] < bigColors)
		for (int iColor = 0; iColor < colors; iColor++)
			ancestersOfColor[color[node]][iColor] += onOfColor[iColor];
	else
		for (int iColor = 0; iColor < bigColors; iColor++)
			ancestersOfColor[color[node]][iColor] += onOfColor[iColor];

	intervalStarts[color[node]].emplace_back(dfsPre[node]);
	intervalEnds[color[node]].emplace_back(dfsPost[node]);

	onOfColor[color[node]]++;
	for (int child : tree[node])
		buildpartialanswers(child, colors, bigColors);
	onOfColor[color[node]]--;
}

long long countbyfusion(int ancCol, int descCol)
{
	int iAnc = 0, maxEnd = -1;
	int ancesterPairs = 0;

	for (int iDesc = 0; iDesc < ofColor[descCol]; iDesc++)
	{
		for (; iAnc < ofColor[ancCol] && intervalStarts[ancCol][iAnc] < intervalStarts[descCol][iDesc]; iAnc++)
			maxEnd = std::max(maxEnd, intervalEnds[ancCol][iAnc]);
		ancesterPairs += (maxEnd > intervalEnds[descCol][iDesc]);
	}

	return ancesterPairs;
}

int main()
{
	int nodes, colors, queries;
	std::cin >> nodes >> colors >> queries;

	for (int iNode = 0; iNode < nodes; iNode++)
	{
		if (iNode > 0)
		{
			int parent; std::cin >> parent;
			tree[parent - 1].emplace_back(iNode);
		}
		
		std::cin >> color[iNode];
		color[iNode]--;
	}

	analysetree(0, 0);
	recolor(colors, nodes);

	int bigColors = 0;
	while (bigColors < colors && ofColor[bigColors] > SQRTN)
		bigColors++;

	for (int iColor = 0; iColor < colors; iColor++)
	{
		if (iColor < bigColors)
			ancestersOfColor[iColor].resize(colors, 0);
		else
			ancestersOfColor[iColor].resize(bigColors, 0);
	}

	buildpartialanswers(0, colors, bigColors);
	for (int iQuery = 0; iQuery < queries; iQuery++)
	{
		int ancCol, descCol;
		std::cin >> ancCol >> descCol;
		ancCol = revOrder[ancCol - 1];
		descCol = revOrder[descCol - 1];

		if (descCol < bigColors || ancCol < bigColors)
			std::cout << ancestersOfColor[descCol][ancCol] << '\n';
		else
			std::cout << countbyfusion(ancCol, descCol) << '\n';
		std::cout << std::flush;
	}

	return 0;
}

Subtask #1

14.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	6776 KB	Output is correct
2	Correct	8 ms	6776 KB	Output is correct
3	Correct	12 ms	6776 KB	Output is correct
4	Correct	14 ms	6904 KB	Output is correct
5	Correct	19 ms	6776 KB	Output is correct
6	Incorrect	21 ms	7288 KB	Output isn't correct
7	Correct	46 ms	7036 KB	Output is correct
8	Correct	53 ms	7160 KB	Output is correct
9	Correct	71 ms	8056 KB	Output is correct
10	Correct	75 ms	8744 KB	Output is correct
11	Correct	145 ms	8184 KB	Output is correct
12	Correct	174 ms	9720 KB	Output is correct
13	Correct	200 ms	8828 KB	Output is correct
14	Correct	180 ms	8616 KB	Output is correct
15	Correct	280 ms	11384 KB	Output is correct

Subtask #2

20.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1016 ms	11776 KB	Output is correct
2	Correct	1086 ms	10664 KB	Output is correct
3	Correct	1620 ms	13684 KB	Output is correct
4	Correct	614 ms	100816 KB	Output is correct
5	Incorrect	693 ms	109332 KB	Output isn't correct
6	Runtime error	170 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
7	Runtime error	185 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
8	Runtime error	214 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
9	Runtime error	285 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
10	Runtime error	310 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
11	Runtime error	363 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
12	Runtime error	355 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
13	Runtime error	332 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Runtime error	368 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Runtime error	337 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Runtime error	329 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	335 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)