oj.uz

답안 #162772

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
162772 2019-11-09T16:51:50 Z faremy Regions (IOI09_regions) C++14
0 / 100
 8000 ms 32240 KB 
#include <iostream>
#include <algorithm>
#include <vector>


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

int onOfColor[MAXR];
std::vector<int> 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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 6776 KB Output isn't correct
2 Incorrect 8 ms 6776 KB Output isn't correct
3 Incorrect 11 ms 6780 KB Output isn't correct
4 Incorrect 10 ms 6904 KB Output isn't correct
5 Incorrect 15 ms 6776 KB Output isn't correct
6 Incorrect 29 ms 6904 KB Output isn't correct
7 Incorrect 27 ms 6776 KB Output isn't correct
8 Incorrect 57 ms 6908 KB Output isn't correct
9 Incorrect 46 ms 7368 KB Output isn't correct
10 Incorrect 76 ms 7464 KB Output isn't correct
11 Incorrect 101 ms 7544 KB Output isn't correct
12 Incorrect 128 ms 8056 KB Output isn't correct
13 Incorrect 140 ms 7800 KB Output isn't correct
14 Incorrect 197 ms 8292 KB Output isn't correct
15 Incorrect 197 ms 10872 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1042 ms 11472 KB Output isn't correct
2 Incorrect 1232 ms 10232 KB Output isn't correct
3 Incorrect 1802 ms 13284 KB Output isn't correct
4 Incorrect 262 ms 8524 KB Output isn't correct
5 Incorrect 426 ms 10104 KB Output isn't correct
6 Incorrect 1911 ms 13224 KB Output isn't correct
7 Incorrect 1509 ms 12160 KB Output isn't correct
8 Incorrect 3993 ms 24020 KB Output isn't correct
9 Incorrect 1798 ms 16428 KB Output isn't correct
10 Incorrect 6100 ms 32240 KB Output isn't correct
11 Incorrect 2984 ms 16400 KB Output isn't correct
12 Incorrect 4309 ms 18528 KB Output isn't correct
13 Incorrect 4673 ms 18556 KB Output isn't correct
14 Execution timed out 8016 ms 21572 KB Time limit exceeded
15 Execution timed out 8009 ms 23368 KB Time limit exceeded
16 Incorrect 7450 ms 28624 KB Output isn't correct
17 Execution timed out 8042 ms 30392 KB Time limit exceeded