Submission #411394

#	Time	Username	Problem	Language	Result	Execution time	Memory
411394		amoo_safar	Mergers (JOI19_mergers)	C++17	100 / 100	1293 ms	85076 KiB

mergers

// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 5e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

int dep[N], par[N], anc[N];
vector<int> G[N];
void DFS(int u, int p, int d){
	dep[u] = d;
	anc[u] = p;
	for(auto adj : G[u])
		if(adj != p)
			DFS(adj, u, d + 1);
}

int Find(int u){
	if(par[u] == u) return u;
	return par[u] = Find(par[u]);
}
void Unite(int u, int v){
	u = Find(u);
	v = Find(v);
	par[u] = v;
}

void Merge(int u, int v){
	// cerr << "!! " << u << ' ' << v << '\n';
	while((u = Find(u)) != (v = Find(v))){
		if(dep[u] < dep[v]) swap(u, v);
		Unite(u, anc[u]);
	}
}
int la[N];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	iota(par, par + N, 0);
	int n, k;
	cin >> n >> k;
	int u, v;
	vector<pll> E;
	for(int i = 1; i < n; i++){
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
		E.pb({u, v});
	}
	DFS(u, 0, 1);
	int s;
	for(int i = 1; i <= n; i++){
		cin >> s;
		if(la[s]) Merge(la[s], i);
		la[s] = i;
	}
	map<int, int> deg;
	for(auto [u, v] : E)
		if(Find(u) != Find(v))
			deg[Find(u)] ++, deg[Find(v)] ++;
	int cnt = 0;
	for(auto [u, d] : deg) cnt += (d == 1);
	// debug(cnt);
	cout << (cnt + 1) / 2 << '\n';
	return 0;
}

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