oj.uz

Submission #311506

# Submission time Handle Problem Language Result Execution time Memory
311506 2020-10-10T14:13:56 Z shivensinha4 Mergers (JOI19_mergers) C++17
0 / 100
 102 ms 46316 KB 
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

const int MXN = 5e5;
vi adj[MXN+1];
int ct[MXN+1], cont[MXN+1], state[MXN+1], n, k;
map<int, int> freq[MXN+1];
int ans = 0;


void dfs(int p, int parent) {
	bool found = false;
	freq[p][state[p]] += 1;
	if (ct[state[p]] != 1) cont[p] += 1;
	
	for (auto i: adj[p]) if (i != parent) {
		dfs(i, p);
		if (!cont[i]) found = true;
		if (!found) {
			//bool swapped = false;
			cont[p] += cont[i];
			if (freq[i].size() > freq[p].size()) {
				swap(freq[i], freq[p]);
				//swapped = true;
			}
			for (auto j: freq[i]) {
				int nv = freq[p][j.first]+j.second;
				freq[p][j.first] = nv;
				if (nv == j.second) continue;
				if (nv == ct[j.first]) ct[p] -= 2;
			}
		}
	}
	
	if (!cont[p] and !found) {
		//cout << p << "'s parent edge found guilty" << endl;
		ans += 1;
	}
}

int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> k;
	for_(i, 0, n-1) {
		int a, b; cin >> a >> b;
		a -= 1; b -= 1;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	for_(i, 0, n) {
		cin >> state[i];
		state[i] -= 1;
		ct[state[i]] += 1;
	}
	
	dfs(0, 0);
	cout << (ans+1)/2 << endl;

	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35584 KB Output is correct
2 Incorrect 22 ms 35712 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35584 KB Output is correct
2 Incorrect 22 ms 35712 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35584 KB Output is correct
2 Incorrect 22 ms 35712 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 46064 KB Output is correct
2 Incorrect 102 ms 46316 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35584 KB Output is correct
2 Incorrect 22 ms 35712 KB Output isn't correct
3 Halted 0 ms 0 KB -