Submission #402992

#	Time	Username	Problem	Language	Result	Execution time	Memory
402992		ritul_kr_singh	Mergers (JOI19_mergers)	C++17	100 / 100	1330 ms	181876 KiB

mergers

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

const int MAXN = 5e5;
array<int, 20> p[MAXN];
vector<int> g[MAXN];
int t0[MAXN], d[MAXN], pre[MAXN], dfsTimer = 0;

void dfs0(int u, int par, int dep){
	t0[u] = dfsTimer++;
	p[u][0] = par, d[u] = dep;
	for(int i=0; i<19; ++i) p[u][i+1] = p[p[u][i]][i];

	for(int v : g[u]) if(v != par) dfs0(v, u, dep + 1);
}

int lca(int u, int v){
	if(d[u] < d[v]) swap(u, v);
	for(int i=0; i<20; ++i) if((d[u]-d[v]) & (1<<i)) u = p[u][i];
	if(u == v) return u;
	for(int i=19; i>=0; --i) if(p[u][i] != p[v][i]) u = p[u][i], v = p[v][i];
	return p[u][0];
}

vector<int> e(MAXN, -1);
int find(int u){
	return e[u] < 0 ? u : e[u] = find(e[u]);
}
void unite(int u, int v){
	u = find(u), v = find(v);
	if(u==v) return;
	if(e[u] > e[v]) swap(u, v);
	e[u] += e[v], e[v] = u;
}

void dfs1(int u){
	for(int v : g[u]){
		if(v == p[u][0]) continue;
		dfs1(v);
		pre[u] += pre[v];
		if(pre[v]) unite(u, v);
	}
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, k, u, v; cin >> n >> k;
	for(int i=1; i<n; ++i){
		cin >> u >> v; --u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	vector<int> c[k];
	for(u=0; u<n; ++u) cin >> v, c[v-1].push_back(u);

	dfs0(0, 0, 0);

	for(auto &i : c){
		sort(i.begin(), i.end(), [&](int x, int y){
			return t0[x] < t0[y];
		});
		i.push_back(i.front());
		for(int j=0; j+1<(int)i.size(); ++j){
			++pre[i[j]];
			++pre[i[j+1]];
			pre[lca(i[j], i[j+1])] -= 2;
		}
	}

	dfs1(0);

	vector<int> h(n);
	for(int u=0; u<n; ++u)
		for(int v : g[u])
			if(find(u) != find(v)) ++h[find(u)], ++h[find(v)];

	int ans = 0;
	for(int u=0; u<n; ++u){
		ans += find(u) == u && h[find(u)] == 2;
	}

	cout << (ans + 1) / 2;
}

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