답안 #311575

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
311575	2020-10-10T16:59:47 Z	shivensinha4	Mergers (JOI19_mergers)	C++17	10 / 100	215 ms	60220 KB

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 (!p and ans and ct[state[p]] == 1 and adj[p].size() == 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

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	35584 KB	Output is correct
2	Correct	25 ms	35576 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	24 ms	35576 KB	Output is correct
7	Correct	25 ms	35584 KB	Output is correct
8	Correct	24 ms	35584 KB	Output is correct
9	Correct	25 ms	35576 KB	Output is correct
10	Correct	25 ms	35580 KB	Output is correct
11	Correct	25 ms	35584 KB	Output is correct
12	Correct	24 ms	35584 KB	Output is correct
13	Correct	24 ms	35584 KB	Output is correct
14	Correct	24 ms	35584 KB	Output is correct
15	Correct	24 ms	35584 KB	Output is correct
16	Correct	25 ms	35616 KB	Output is correct
17	Correct	24 ms	35584 KB	Output is correct
18	Correct	25 ms	35584 KB	Output is correct
19	Correct	26 ms	35576 KB	Output is correct
20	Correct	24 ms	35588 KB	Output is correct
21	Correct	25 ms	35584 KB	Output is correct
22	Correct	25 ms	35704 KB	Output is correct
23	Correct	25 ms	35576 KB	Output is correct
24	Correct	24 ms	35584 KB	Output is correct

Subtask #2

0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	35584 KB	Output is correct
2	Correct	25 ms	35576 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	24 ms	35576 KB	Output is correct
7	Correct	25 ms	35584 KB	Output is correct
8	Correct	24 ms	35584 KB	Output is correct
9	Correct	25 ms	35576 KB	Output is correct
10	Correct	25 ms	35580 KB	Output is correct
11	Correct	25 ms	35584 KB	Output is correct
12	Correct	24 ms	35584 KB	Output is correct
13	Correct	24 ms	35584 KB	Output is correct
14	Correct	24 ms	35584 KB	Output is correct
15	Correct	24 ms	35584 KB	Output is correct
16	Correct	25 ms	35616 KB	Output is correct
17	Correct	24 ms	35584 KB	Output is correct
18	Correct	25 ms	35584 KB	Output is correct
19	Correct	26 ms	35576 KB	Output is correct
20	Correct	24 ms	35588 KB	Output is correct
21	Correct	25 ms	35584 KB	Output is correct
22	Correct	25 ms	35704 KB	Output is correct
23	Correct	25 ms	35576 KB	Output is correct
24	Correct	24 ms	35584 KB	Output is correct
25	Correct	25 ms	35584 KB	Output is correct
26	Correct	30 ms	36216 KB	Output is correct
27	Correct	26 ms	35968 KB	Output is correct
28	Correct	28 ms	36344 KB	Output is correct
29	Correct	29 ms	36472 KB	Output is correct
30	Correct	28 ms	36096 KB	Output is correct
31	Correct	25 ms	35576 KB	Output is correct
32	Correct	30 ms	36480 KB	Output is correct
33	Correct	25 ms	35584 KB	Output is correct
34	Correct	26 ms	35832 KB	Output is correct
35	Correct	29 ms	36352 KB	Output is correct
36	Incorrect	26 ms	35832 KB	Output isn't correct
37	Halted	0 ms	0 KB	-

Subtask #3

0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	35584 KB	Output is correct
2	Correct	25 ms	35576 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	24 ms	35576 KB	Output is correct
7	Correct	25 ms	35584 KB	Output is correct
8	Correct	24 ms	35584 KB	Output is correct
9	Correct	25 ms	35576 KB	Output is correct
10	Correct	25 ms	35580 KB	Output is correct
11	Correct	25 ms	35584 KB	Output is correct
12	Correct	24 ms	35584 KB	Output is correct
13	Correct	24 ms	35584 KB	Output is correct
14	Correct	24 ms	35584 KB	Output is correct
15	Correct	24 ms	35584 KB	Output is correct
16	Correct	25 ms	35616 KB	Output is correct
17	Correct	24 ms	35584 KB	Output is correct
18	Correct	25 ms	35584 KB	Output is correct
19	Correct	26 ms	35576 KB	Output is correct
20	Correct	24 ms	35588 KB	Output is correct
21	Correct	25 ms	35584 KB	Output is correct
22	Correct	25 ms	35704 KB	Output is correct
23	Correct	25 ms	35576 KB	Output is correct
24	Correct	24 ms	35584 KB	Output is correct
25	Correct	24 ms	35584 KB	Output is correct
26	Correct	104 ms	46064 KB	Output is correct
27	Correct	160 ms	52472 KB	Output is correct
28	Correct	26 ms	35968 KB	Output is correct
29	Correct	25 ms	35584 KB	Output is correct
30	Correct	24 ms	35584 KB	Output is correct
31	Correct	123 ms	45964 KB	Output is correct
32	Correct	27 ms	35832 KB	Output is correct
33	Correct	151 ms	60220 KB	Output is correct
34	Correct	154 ms	51320 KB	Output is correct
35	Incorrect	27 ms	35840 KB	Output isn't correct
36	Halted	0 ms	0 KB	-

Subtask #4

0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	101 ms	44528 KB	Output is correct
2	Correct	192 ms	49416 KB	Output is correct
3	Correct	28 ms	36224 KB	Output is correct
4	Correct	27 ms	35832 KB	Output is correct
5	Correct	26 ms	35584 KB	Output is correct
6	Correct	25 ms	35584 KB	Output is correct
7	Correct	26 ms	35832 KB	Output is correct
8	Correct	215 ms	59208 KB	Output is correct
9	Incorrect	27 ms	35840 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	35584 KB	Output is correct
2	Correct	25 ms	35576 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	24 ms	35576 KB	Output is correct
7	Correct	25 ms	35584 KB	Output is correct
8	Correct	24 ms	35584 KB	Output is correct
9	Correct	25 ms	35576 KB	Output is correct
10	Correct	25 ms	35580 KB	Output is correct
11	Correct	25 ms	35584 KB	Output is correct
12	Correct	24 ms	35584 KB	Output is correct
13	Correct	24 ms	35584 KB	Output is correct
14	Correct	24 ms	35584 KB	Output is correct
15	Correct	24 ms	35584 KB	Output is correct
16	Correct	25 ms	35616 KB	Output is correct
17	Correct	24 ms	35584 KB	Output is correct
18	Correct	25 ms	35584 KB	Output is correct
19	Correct	26 ms	35576 KB	Output is correct
20	Correct	24 ms	35588 KB	Output is correct
21	Correct	25 ms	35584 KB	Output is correct
22	Correct	25 ms	35704 KB	Output is correct
23	Correct	25 ms	35576 KB	Output is correct
24	Correct	24 ms	35584 KB	Output is correct
25	Correct	25 ms	35584 KB	Output is correct
26	Correct	30 ms	36216 KB	Output is correct
27	Correct	26 ms	35968 KB	Output is correct
28	Correct	28 ms	36344 KB	Output is correct
29	Correct	29 ms	36472 KB	Output is correct
30	Correct	28 ms	36096 KB	Output is correct
31	Correct	25 ms	35576 KB	Output is correct
32	Correct	30 ms	36480 KB	Output is correct
33	Correct	25 ms	35584 KB	Output is correct
34	Correct	26 ms	35832 KB	Output is correct
35	Correct	29 ms	36352 KB	Output is correct
36	Incorrect	26 ms	35832 KB	Output isn't correct
37	Halted	0 ms	0 KB	-