Submission #819311

#	Time	Username	Problem	Language	Result	Execution time	Memory
819311		AdamGS	Mergers (JOI19_mergers)	C++17	100 / 100	804 ms	104040 KiB

mergers

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e5+7;
vector<int>V[LIM], P[LIM];
int T[LIM], odl[LIM], F[LIM], oc[LIM], deg[LIM];
void DFS(int x, int o) {
	for(auto i : V[x]) if(i!=o) {
		odl[i]=odl[x]+1;
		oc[i]=x;
		DFS(i, x);
	}
}
int fnd(int x) {
	if(F[x]==x) return x;
	return F[x]=fnd(F[x]);
}
void uni(int a, int b) {
	if(fnd(a)==fnd(b)) return;
	F[fnd(b)]=fnd(a);
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, k;
	cin >> n >> k;
	rep(i, n-1) {
		int a, b;
		cin >> a >> b; --a; --b;
		V[a].pb(b);
		V[b].pb(a);
	}
	DFS(0, 0);
	rep(i, n) {
		cin >> T[i]; --T[i];
		P[T[i]].pb(i);
		F[i]=i;
	}
	rep(i, k) {
		set<pair<int,int>>S;
		for(auto j : P[i]) S.insert({odl[fnd(j)], fnd(j)});
		while(S.size()>1) {
			auto it=S.end(); --it;
			auto p=*it;
			S.erase(it);
			uni(oc[p.nd], p.nd);
			S.insert({odl[fnd(p.nd)], fnd(p.nd)});
		}
	}
	rep(i, n) for(auto j : V[i]) if(fnd(i)!=fnd(j)) ++deg[fnd(j)];
	int ans=0;
	rep(i, n) if(deg[i]==1) ++ans;
	cout << (ans+1)/2 << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30