Submission #114577

#	Time	Username	Problem	Language	Result	Execution time	Memory
114577		tincamatei	Mergers (JOI19_mergers)	C++14	100 / 100	1620 ms	85228 KiB

mergers

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500000;
const int MAX_K = MAX_N;

vector<int> graph[1+MAX_N];
int color[1+MAX_N], fr[1+MAX_K], subarb[1+MAX_K];
int criticalsubarb[1+MAX_N];
int nrleaves, criticalEdges;
bool intree[1+MAX_N];

void dfs(int nod, int papa = 0) {
	subarb[nod] = 1;
	for(auto it: graph[nod])
		if(it != papa) {
			dfs(it, nod);
			subarb[nod] += subarb[it];
		}
}

struct CriticalEdgeChecker {
	vector<int> nodehistory;
	int freq[1+MAX_K], fullsides, K;

	CriticalEdgeChecker(int _K):K(_K) {
		fullsides = K;
		for(int i = 0; i <= MAX_K; ++i)
			freq[i] = 0;
	}

	void insert(int nod) {
		if(freq[color[nod]] == 0)
			fullsides--;
		freq[color[nod]]++;
		if(freq[color[nod]] == fr[color[nod]])
			++fullsides;
		nodehistory.push_back(nod);
	}
	
	void erase(int nod) {
		if(freq[color[nod]] == fr[color[nod]])
			--fullsides;
		freq[color[nod]]--;
		if(freq[color[nod]] == 0)
			++fullsides;
	}

	void clear() {
		for(auto it: nodehistory)
			erase(it);
		nodehistory.clear();
	}

	bool isCritical() {
		return fullsides == K;
	}
} *criticalEdge;

void pourDfs(int nod, int papa = 0) {
	criticalEdge->insert(nod);
	for(auto it: graph[nod])
		if(it != papa)
			pourDfs(it, nod);
}

void heavyDfs(int nod, int papa = 0) {
	int heavySon = -1;
	for(auto it: graph[nod])
		if(it != papa && (heavySon == -1 || (heavySon != -1 && subarb[it] > subarb[heavySon])))
			heavySon = it;

	if(heavySon != -1) {
		for(auto it: graph[nod])
			if(it != papa && it != heavySon) {
				criticalEdge->clear();
				heavyDfs(it, nod);
				if(criticalEdge->isCritical()) {
					criticalsubarb[nod]++;
					criticalEdges++;
					intree[it] = true;
				}
			}

		criticalEdge->clear();
		heavyDfs(heavySon, nod);
		if(criticalEdge->isCritical()) {
			criticalsubarb[nod]++;
			criticalEdges++;
			intree[heavySon] = true;
		}
		
		for(auto it: graph[nod])
			if(it != papa && it != heavySon)
				pourDfs(it, nod);
	}
	criticalEdge->insert(nod);
}

int buildTree(int nod, int papa = 0) {
	int degree = (papa != 0); // degree from above
	for(auto it: graph[nod])
		if(it != papa)
			degree += buildTree(it, nod);

	if(intree[nod]) {
		if(degree == 1)
			++nrleaves;
		return 1;
	} else
		return degree - (papa != 0);
}

int main() {
	int N, K;
	scanf("%d%d", &N, &K);
	criticalEdge = new CriticalEdgeChecker(K);

	for(int i = 0; i < N - 1; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	for(int i = 1; i <= N; ++i) {
		scanf("%d", &color[i]);
		fr[color[i]]++;
	}

	dfs(1);
	heavyDfs(1);
	
	intree[1] = true;
	buildTree(1);

	printf("%d", (nrleaves + 1) / 2);

	return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:122:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &color[i]);
   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30