Submission #311556

#	Time	Username	Problem	Language	Result	Execution time	Memory
311556		shivensinha4	Mergers (JOI19_mergers)	C++17	0 / 100	193 ms	49392 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;
bool fnd[MXN+1];
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 (fnd[i]) found = true;
		if (true) {
			cont[p] += cont[i];
			if (freq[i].size() > freq[p].size()) swap(freq[i], freq[p]);
			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]) cont[p] -= 2;
				else cont[p] -= 1;
			}
		}
	}
	
	//cout << endl << endl;
	//cout << "... " << p+1 << endl;
	//for (auto i: freq[p]) cout << i.first+1 << " -> " << i.second << endl;
	//cout << p+1 << " has " << cont[p] << endl;
	//if (cont[p] == 0) cout << p+1 << " has cont 0 " << found << endl;
	
	if (found) fnd[p] = true;
	else if ((!cont[p]) and p) {
		//cout << p+1 << "'s parent edge found guilty" << endl;
		fnd[p] = true;
		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 << endl;
	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