oj.uz

답안 #162770

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

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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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)