oj.uz

답안 #311526

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
311526 2020-10-10T14:52:50 Z shivensinha4 Mergers (JOI19_mergers) C++17
0 / 100
 196 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 (found) fnd[p] = true;
	else if (!cont[p] and p != 0) {
		//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

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 35584 KB Output is correct
2 Correct 23 ms 35584 KB Output is correct
3 Correct 24 ms 35584 KB Output is correct
4 Correct 22 ms 35584 KB Output is correct
5 Correct 33 ms 35576 KB Output is correct
6 Correct 21 ms 35584 KB Output is correct
7 Correct 25 ms 35584 KB Output is correct
8 Correct 22 ms 35584 KB Output is correct
9 Correct 25 ms 35576 KB Output is correct
10 Correct 24 ms 35712 KB Output is correct
11 Correct 25 ms 35584 KB Output is correct
12 Correct 22 ms 35584 KB Output is correct
13 Correct 23 ms 35584 KB Output is correct
14 Correct 23 ms 35584 KB Output is correct
15 Correct 26 ms 35576 KB Output is correct
16 Incorrect 25 ms 35584 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 35584 KB Output is correct
2 Correct 23 ms 35584 KB Output is correct
3 Correct 24 ms 35584 KB Output is correct
4 Correct 22 ms 35584 KB Output is correct
5 Correct 33 ms 35576 KB Output is correct
6 Correct 21 ms 35584 KB Output is correct
7 Correct 25 ms 35584 KB Output is correct
8 Correct 22 ms 35584 KB Output is correct
9 Correct 25 ms 35576 KB Output is correct
10 Correct 24 ms 35712 KB Output is correct
11 Correct 25 ms 35584 KB Output is correct
12 Correct 22 ms 35584 KB Output is correct
13 Correct 23 ms 35584 KB Output is correct
14 Correct 23 ms 35584 KB Output is correct
15 Correct 26 ms 35576 KB Output is correct
16 Incorrect 25 ms 35584 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 35584 KB Output is correct
2 Correct 23 ms 35584 KB Output is correct
3 Correct 24 ms 35584 KB Output is correct
4 Correct 22 ms 35584 KB Output is correct
5 Correct 33 ms 35576 KB Output is correct
6 Correct 21 ms 35584 KB Output is correct
7 Correct 25 ms 35584 KB Output is correct
8 Correct 22 ms 35584 KB Output is correct
9 Correct 25 ms 35576 KB Output is correct
10 Correct 24 ms 35712 KB Output is correct
11 Correct 25 ms 35584 KB Output is correct
12 Correct 22 ms 35584 KB Output is correct
13 Correct 23 ms 35584 KB Output is correct
14 Correct 23 ms 35584 KB Output is correct
15 Correct 26 ms 35576 KB Output is correct
16 Incorrect 25 ms 35584 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 44632 KB Output is correct
2 Incorrect 196 ms 49388 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 35584 KB Output is correct
2 Correct 23 ms 35584 KB Output is correct
3 Correct 24 ms 35584 KB Output is correct
4 Correct 22 ms 35584 KB Output is correct
5 Correct 33 ms 35576 KB Output is correct
6 Correct 21 ms 35584 KB Output is correct
7 Correct 25 ms 35584 KB Output is correct
8 Correct 22 ms 35584 KB Output is correct
9 Correct 25 ms 35576 KB Output is correct
10 Correct 24 ms 35712 KB Output is correct
11 Correct 25 ms 35584 KB Output is correct
12 Correct 22 ms 35584 KB Output is correct
13 Correct 23 ms 35584 KB Output is correct
14 Correct 23 ms 35584 KB Output is correct
15 Correct 26 ms 35576 KB Output is correct
16 Incorrect 25 ms 35584 KB Output isn't correct
17 Halted 0 ms 0 KB -