Submission #162786

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
162786	2019-11-09T17:35:24 Z	faremy	Regions (IOI09_regions)	C++14	100 / 100	4258 ms	42616 KB

regions

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstdlib>


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

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];
std::stack<int> fusionStack;


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]]--;
}

int merge(int elem)
{
	int occChange = (elem < 0);
	while (!fusionStack.empty() && std::abs(fusionStack.top()) < std::abs(elem))
	{
		occChange -= (fusionStack.top() < 0);
		fusionStack.pop();
	}

	fusionStack.emplace(elem);
	return occChange;
}

int countbyfusion(int ancCol, int descCol)
{
	int iAnc = 0, ofAncCol = 0;
	int ancesterPairs = 0;

	for (int iDesc = 0; iDesc < ofColor[descCol]; iDesc++)
	{
		for (; iAnc < ofColor[ancCol] && intervalStarts[ancCol][iAnc] < intervalStarts[descCol][iDesc]; iAnc++)
			ofAncCol += merge(-intervalEnds[ancCol][iAnc]);
		ofAncCol += merge(intervalEnds[descCol][iDesc]);
		ancesterPairs += ofAncCol;
	}

	while (!fusionStack.empty())
		fusionStack.pop();
	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, 1);
	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

15.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	10 ms	6776 KB	Output is correct
4	Correct	12 ms	6904 KB	Output is correct
5	Correct	12 ms	6824 KB	Output is correct
6	Correct	42 ms	7032 KB	Output is correct
7	Correct	43 ms	6776 KB	Output is correct
8	Correct	30 ms	6904 KB	Output is correct
9	Correct	56 ms	7288 KB	Output is correct
10	Correct	117 ms	7416 KB	Output is correct
11	Correct	157 ms	7544 KB	Output is correct
12	Correct	184 ms	8020 KB	Output is correct
13	Correct	219 ms	7720 KB	Output is correct
14	Correct	288 ms	8360 KB	Output is correct
15	Correct	355 ms	10872 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1291 ms	11516 KB	Output is correct
2	Correct	1270 ms	10280 KB	Output is correct
3	Correct	2496 ms	13244 KB	Output is correct
4	Correct	363 ms	8552 KB	Output is correct
5	Correct	455 ms	10232 KB	Output is correct
6	Correct	919 ms	16656 KB	Output is correct
7	Correct	1776 ms	13196 KB	Output is correct
8	Correct	1634 ms	31736 KB	Output is correct
9	Correct	2411 ms	16632 KB	Output is correct
10	Correct	3536 ms	42616 KB	Output is correct
11	Correct	4258 ms	16548 KB	Output is correct
12	Correct	2089 ms	18624 KB	Output is correct
13	Correct	2624 ms	18872 KB	Output is correct
14	Correct	3465 ms	25376 KB	Output is correct
15	Correct	4051 ms	23736 KB	Output is correct
16	Correct	3751 ms	29000 KB	Output is correct
17	Correct	4138 ms	33964 KB	Output is correct