Submission #311506

#	Time	Username	Problem	Language	Result	Execution time	Memory
311506		shivensinha4	Mergers (JOI19_mergers)	C++17	0 / 100	102 ms	46316 KiB

mergers

#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
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30