Submission #375965

#	Time	Username	Problem	Language	Result	Execution time	Memory
375965		pit4h	Mergers (JOI19_mergers)	C++14	0 / 100	65 ms	18660 KiB

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
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30