oj.uz

Submission #311556

# Submission time Handle Problem Language Result Execution time Memory
311556 2020-10-10T16:09:34 Z shivensinha4 Mergers (JOI19_mergers) C++17
0 / 100
 193 ms 49392 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 (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 21 ms 35584 KB Output is correct
2 Correct 22 ms 35584 KB Output is correct
3 Correct 22 ms 35584 KB Output is correct
4 Correct 22 ms 35584 KB Output is correct
5 Correct 21 ms 35584 KB Output is correct
6 Correct 22 ms 35584 KB Output is correct
7 Correct 22 ms 35584 KB Output is correct
8 Correct 22 ms 35584 KB Output is correct
9 Correct 21 ms 35576 KB Output is correct
10 Correct 22 ms 35644 KB Output is correct
11 Correct 21 ms 35584 KB Output is correct
12 Correct 22 ms 35584 KB Output is correct
13 Correct 22 ms 35584 KB Output is correct
14 Correct 22 ms 35584 KB Output is correct
15 Correct 22 ms 35584 KB Output is correct
16 Incorrect 22 ms 35584 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35584 KB Output is correct
2 Correct 22 ms 35584 KB Output is correct
3 Correct 22 ms 35584 KB Output is correct
4 Correct 22 ms 35584 KB Output is correct
5 Correct 21 ms 35584 KB Output is correct
6 Correct 22 ms 35584 KB Output is correct
7 Correct 22 ms 35584 KB Output is correct
8 Correct 22 ms 35584 KB Output is correct
9 Correct 21 ms 35576 KB Output is correct
10 Correct 22 ms 35644 KB Output is correct
11 Correct 21 ms 35584 KB Output is correct
12 Correct 22 ms 35584 KB Output is correct
13 Correct 22 ms 35584 KB Output is correct
14 Correct 22 ms 35584 KB Output is correct
15 Correct 22 ms 35584 KB Output is correct
16 Incorrect 22 ms 35584 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35584 KB Output is correct
2 Correct 22 ms 35584 KB Output is correct
3 Correct 22 ms 35584 KB Output is correct
4 Correct 22 ms 35584 KB Output is correct
5 Correct 21 ms 35584 KB Output is correct
6 Correct 22 ms 35584 KB Output is correct
7 Correct 22 ms 35584 KB Output is correct
8 Correct 22 ms 35584 KB Output is correct
9 Correct 21 ms 35576 KB Output is correct
10 Correct 22 ms 35644 KB Output is correct
11 Correct 21 ms 35584 KB Output is correct
12 Correct 22 ms 35584 KB Output is correct
13 Correct 22 ms 35584 KB Output is correct
14 Correct 22 ms 35584 KB Output is correct
15 Correct 22 ms 35584 KB Output is correct
16 Incorrect 22 ms 35584 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 44632 KB Output is correct
2 Incorrect 193 ms 49392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35584 KB Output is correct
2 Correct 22 ms 35584 KB Output is correct
3 Correct 22 ms 35584 KB Output is correct
4 Correct 22 ms 35584 KB Output is correct
5 Correct 21 ms 35584 KB Output is correct
6 Correct 22 ms 35584 KB Output is correct
7 Correct 22 ms 35584 KB Output is correct
8 Correct 22 ms 35584 KB Output is correct
9 Correct 21 ms 35576 KB Output is correct
10 Correct 22 ms 35644 KB Output is correct
11 Correct 21 ms 35584 KB Output is correct
12 Correct 22 ms 35584 KB Output is correct
13 Correct 22 ms 35584 KB Output is correct
14 Correct 22 ms 35584 KB Output is correct
15 Correct 22 ms 35584 KB Output is correct
16 Incorrect 22 ms 35584 KB Output isn't correct
17 Halted 0 ms 0 KB -