oj.uz

답안 #162759

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
162759 2019-11-09T16:01:19 Z faremy Regions (IOI09_regions) C++14
0 / 100
 3407 ms 42504 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];

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()
{
	std::ios::sync_with_stdio(false);
	std::cout.tie(nullptr);
	std::cin.tie(nullptr);

	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] << std::endl;
		else
			std::cout << countbyfusion(ancCol, descCol) << std::endl;
	}

	return 0;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 6776 KB Output isn't correct
2 Incorrect 7 ms 6776 KB Output isn't correct
3 Incorrect 9 ms 6776 KB Output isn't correct
4 Incorrect 13 ms 6776 KB Output isn't correct
5 Incorrect 17 ms 6776 KB Output isn't correct
6 Incorrect 16 ms 6904 KB Output isn't correct
7 Incorrect 36 ms 6904 KB Output isn't correct
8 Incorrect 29 ms 6952 KB Output isn't correct
9 Incorrect 55 ms 7416 KB Output isn't correct
10 Incorrect 95 ms 7316 KB Output isn't correct
11 Incorrect 78 ms 7668 KB Output isn't correct
12 Incorrect 141 ms 8216 KB Output isn't correct
13 Incorrect 182 ms 7860 KB Output isn't correct
14 Incorrect 176 ms 8444 KB Output isn't correct
15 Incorrect 230 ms 10872 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 720 ms 11532 KB Output isn't correct
2 Incorrect 1086 ms 10364 KB Output isn't correct
3 Incorrect 1421 ms 13224 KB Output isn't correct
4 Incorrect 284 ms 8480 KB Output isn't correct
5 Incorrect 387 ms 10104 KB Output isn't correct
6 Incorrect 808 ms 16632 KB Output isn't correct
7 Incorrect 1022 ms 13072 KB Output isn't correct
8 Incorrect 1194 ms 31736 KB Output isn't correct
9 Incorrect 1379 ms 16620 KB Output isn't correct
10 Incorrect 2324 ms 42504 KB Output isn't correct
11 Incorrect 2233 ms 16624 KB Output isn't correct
12 Incorrect 1381 ms 18584 KB Output isn't correct
13 Incorrect 1644 ms 18876 KB Output isn't correct
14 Incorrect 2778 ms 25220 KB Output isn't correct
15 Incorrect 2677 ms 23632 KB Output isn't correct
16 Incorrect 2890 ms 28852 KB Output isn't correct
17 Incorrect 3407 ms 33884 KB Output isn't correct