제출 #1291060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291060		Jawad_Akbar_JJ	Mergers (JOI19_mergers)	C++20	100 / 100	816 ms	106580 KiB

mergers

#include <iostream>
#include <vector>

using namespace std;
const int N = (1<<19);
vector<int> nei[N];
int Par[N][20], hei[N], c[N], ch[N], cnt[N], Mn[N], lca[N];

void dfs(int u, int p){
	Par[u][0] = p;
	hei[u] = hei[p] + 1;
	for (int i=0;i<18;i++)
		Par[u][i+1] = Par[Par[u][i]][i];

	for (int i : nei[u]){
		if (i != p)
			dfs(i, u);
	}
}


void dfs2(int u, int p){
	for (int i : nei[u]){
		if (i == p)
			continue;
		dfs2(i, u);
		ch[u] += ch[i];
		cnt[u] += cnt[i];
		Mn[u] = min(Mn[u], Mn[i]);
	}
	if (Mn[u] == hei[u] and u - 1)
		ch[u] = 1;

	if (Mn[u] == hei[u] and cnt[u] == 0)
		cnt[u] = 1;
	
}

int LCA(int u, int v){
	if (hei[u] > hei[v])
		swap(u, v);
	for (int i=18;i>=0;i--){
		if (hei[u] + (1<<i) <= hei[v])
			v = Par[v][i];
	}
	for (int i=18;i>=0;i--){
		if (Par[u][i] != Par[v][i])
			u = Par[u][i], v = Par[v][i];
	}
	return (u == v ? u : Par[u][0]);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m;
	cin>>n>>m;

	for (int i=1;i<n;i++){
		int a, b;
		cin>>a>>b;
		nei[a].push_back(b);
		nei[b].push_back(a);
	}

	dfs(1, 0);

	for (int i=1;i<=n;i++){
		cin>>c[i];
		if (lca[c[i]] == 0)
			lca[c[i]] = i;
		else
			lca[c[i]] = LCA(lca[c[i]], i);
	}

	for (int i=1;i<=n;i++)
		Mn[i] = hei[lca[c[i]]];

	dfs2(1, 0);

	if (ch[1] == 0)
		cout<<0<<'\n';
	else if (ch[1] == 1)
		cout<<(cnt[1] + 2) / 2<<'\n';
	else
		cout<<(cnt[1] + 1) / 2<<'\n';
}

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