oj.uz

Submission #311572

# Submission time Handle Problem Language Result Execution time Memory
311572 2020-10-10T16:56:35 Z shivensinha4 Mergers (JOI19_mergers) C++17
0 / 100
 218 ms 49388 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;
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 (!p and ans and ct[state[p]] == 1) {
		ans += 1;
		return;
	}
	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.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 35576 KB Output is correct
2 Correct 25 ms 35584 KB Output is correct
3 Correct 24 ms 35584 KB Output is correct
4 Correct 25 ms 35584 KB Output is correct
5 Correct 25 ms 35584 KB Output is correct
6 Correct 25 ms 35584 KB Output is correct
7 Correct 30 ms 35584 KB Output is correct
8 Correct 24 ms 35584 KB Output is correct
9 Incorrect 25 ms 35584 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 35576 KB Output is correct
2 Correct 25 ms 35584 KB Output is correct
3 Correct 24 ms 35584 KB Output is correct
4 Correct 25 ms 35584 KB Output is correct
5 Correct 25 ms 35584 KB Output is correct
6 Correct 25 ms 35584 KB Output is correct
7 Correct 30 ms 35584 KB Output is correct
8 Correct 24 ms 35584 KB Output is correct
9 Incorrect 25 ms 35584 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 35576 KB Output is correct
2 Correct 25 ms 35584 KB Output is correct
3 Correct 24 ms 35584 KB Output is correct
4 Correct 25 ms 35584 KB Output is correct
5 Correct 25 ms 35584 KB Output is correct
6 Correct 25 ms 35584 KB Output is correct
7 Correct 30 ms 35584 KB Output is correct
8 Correct 24 ms 35584 KB Output is correct
9 Incorrect 25 ms 35584 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 44536 KB Output is correct
2 Correct 218 ms 49388 KB Output is correct
3 Correct 31 ms 36216 KB Output is correct
4 Correct 25 ms 35840 KB Output is correct
5 Incorrect 23 ms 35584 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 35576 KB Output is correct
2 Correct 25 ms 35584 KB Output is correct
3 Correct 24 ms 35584 KB Output is correct
4 Correct 25 ms 35584 KB Output is correct
5 Correct 25 ms 35584 KB Output is correct
6 Correct 25 ms 35584 KB Output is correct
7 Correct 30 ms 35584 KB Output is correct
8 Correct 24 ms 35584 KB Output is correct
9 Incorrect 25 ms 35584 KB Output isn't correct
10 Halted 0 ms 0 KB -