oj.uz

답안 #162771

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
162771 2019-11-09T16:48:25 Z faremy Regions (IOI09_regions) C++14
34 / 100
 1756 ms 131076 KB 
#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];

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
14.0 / 15.0

# 결과 실행 시간 메모리 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 10 ms 6904 KB Output is correct
5 Correct 18 ms 6776 KB Output is correct
6 Incorrect 28 ms 7160 KB Output isn't correct
7 Correct 24 ms 6904 KB Output is correct
8 Correct 64 ms 7160 KB Output is correct
9 Correct 81 ms 7672 KB Output is correct
10 Correct 142 ms 7928 KB Output is correct
11 Correct 151 ms 7928 KB Output is correct
12 Correct 225 ms 8952 KB Output is correct
13 Correct 221 ms 8264 KB Output is correct
14 Correct 266 ms 8560 KB Output is correct
15 Correct 318 ms 11144 KB Output is correct

Subtask #2
20.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1077 ms 11612 KB Output is correct
2 Correct 1193 ms 10396 KB Output is correct
3 Correct 1756 ms 13536 KB Output is correct
4 Correct 1081 ms 54612 KB Output is correct
5 Incorrect 1548 ms 59796 KB Output isn't correct
6 Runtime error 176 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 195 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 219 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 320 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 299 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 351 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 351 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 390 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 369 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 351 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 344 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 331 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)