oj.uz

Submission #114569

# Submission time Handle Problem Language Result Execution time Memory
114569 2019-06-01T19:33:15 Z tincamatei Mergers (JOI19_mergers) C++14
0 / 100
 141 ms 21328 KB 
#include <bits/stdc++.h>

using namespace std;

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

vector<int> graph[MAX_N];
int color[1+MAX_N], fr[1+MAX_K], frsub[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[nod] = intree[it] = true;
				}
			}

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

void getInducedLeaves(int nod, int papa = 0) {
	for(auto it: graph[nod])
		if(it != papa) {
			getInducedLeaves(it, nod);
			criticalsubarb[nod] += criticalsubarb[it];
		}
	
	if((criticalsubarb[nod] == 0 || criticalsubarb[nod] == criticalEdges - 1) && intree[nod]) {
		++nrleaves;
	}
}

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);
	getInducedLeaves(1);

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

	return 0;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:116: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:121: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:127:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &color[i]);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14080 KB Output is correct
2 Correct 12 ms 14080 KB Output is correct
3 Incorrect 13 ms 14080 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14080 KB Output is correct
2 Correct 12 ms 14080 KB Output is correct
3 Incorrect 13 ms 14080 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14080 KB Output is correct
2 Correct 12 ms 14080 KB Output is correct
3 Incorrect 13 ms 14080 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 20592 KB Output is correct
2 Correct 77 ms 21328 KB Output is correct
3 Correct 16 ms 14336 KB Output is correct
4 Correct 15 ms 14336 KB Output is correct
5 Correct 14 ms 14080 KB Output is correct
6 Correct 13 ms 14080 KB Output is correct
7 Correct 16 ms 14308 KB Output is correct
8 Correct 141 ms 21156 KB Output is correct
9 Correct 16 ms 14328 KB Output is correct
10 Incorrect 117 ms 20852 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14080 KB Output is correct
2 Correct 12 ms 14080 KB Output is correct
3 Incorrect 13 ms 14080 KB Output isn't correct
4 Halted 0 ms 0 KB -