Submission #375965

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
375965	2021-03-10T11:00:32 Z	pit4h	Mergers (JOI19_mergers)	C++14	0 / 100	65 ms	18660 KB

mergers

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#ifndef LOCAL
#define cerr if(0)cerr
#endif
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using pii = pair<int, int>;

const int MAXN = 5e5+1;
int n, k, s[MAXN];
vector<int> g[MAXN];
int pre[MAXN], subt[MAXN], nr;
int maxp[MAXN], minp[MAXN];
int max_subt[MAXN], min_subt[MAXN];
bool bad[MAXN];
int cnt[MAXN], last;
int leaves;
void dfs(int x, int p) {
	pre[x] = ++nr;
	subt[x] = 1;
	for(int i: g[x]) {
		if(i!=p) {
			dfs(i, x);
			subt[x] += subt[i];
		}
	}
}
void solve(int x, int p) {
	max_subt[x] = maxp[s[x]];
	min_subt[x] = minp[s[x]];
	for(int i: g[x]) {
		if(i!=p) {
			solve(i, x);
			if(bad[i]) {
				bad[x] = 1;
				cnt[x]++;
			}
			max_subt[x] = max(max_subt[x], max_subt[i]);
			min_subt[x] = min(min_subt[x], min_subt[i]);
		}
	}
	if(x!=1 && !bad[x] && (min_subt[x] >= pre[x] && max_subt[x] <= pre[x]+subt[x]-1)) {
		bad[x] = 1;
		leaves++;
		last = p;
	}
	if(cnt[x] > 1) {
		last = 0;
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>k;
	for(int i=0; i<n-1; ++i) {
		int a, b; cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i=1; i<=n; ++i) {
		cin>>s[i];
	}
	dfs(1, 1);
	for(int i=1; i<=n; ++i) {
		maxp[s[i]] = max(maxp[s[i]], pre[i]);	
		minp[s[i]] = min(minp[s[i]], pre[i]);
		if(minp[s[i]]==0) minp[s[i]] = pre[i];
	}
	solve(1, 1);
	if(leaves>0) {
		if(last!=0) {
			leaves++;
		}
		cout<<(leaves-1)/2+1<<'\n';
	}
	else cout<<0<<'\n';
}

Subtask #1

0 / 10.0

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

Subtask #2

0 / 24.0

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

Subtask #3

0 / 14.0

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

Subtask #4

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	17764 KB	Output is correct
2	Incorrect	65 ms	18660 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

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