Submission #138077

#	Time	Username	Problem	Language	Result	Execution time	Memory
138077		anayk	Mergers (JOI19_mergers)	C++14	100 / 100	2197 ms	110844 KiB

mergers

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>

#define MAXN 500005
#define LOGM 22

int par[LOGM][MAXN];
int p[MAXN];
int lev[MAXN];
int mark[MAXN];
int type[MAXN];
int tar[MAXN];
std::vector<int> Adj[MAXN];
std::vector<int> coll[MAXN];
std::pair<int, int> ord[MAXN];
std::queue<int> q;
std::stack<std::pair<int, int> > s;
int deg[MAXN];

int find(int u)
{
	if(p[u] < 0)
		return u;
	else
		return p[u] = find(p[u]);
}

void merge(int u, int v)
{
	u = find(u);
	v = find(v);
	
	if(u == v)
		return;
	
	p[u] += p[v];
	p[v] = u;
}

void dfs()
{
	while(!s.empty())
	{
		int u = s.top().first;
		int p;
		p = s.top().second;
		
		lev[u] = 0;
		if(p)
		{
			par[0][u] = p;
			lev[u] = lev[p]+1;
		}
		
		for(int i = 1; i < LOGM; i++)
		{
			if(par[i-1][u] > 0)
				par[i][u] = par[i-1][par[i-1][u]];
		}
		
		s.pop();
		
		for(int v : Adj[u])
		{
			if(v == p)
				continue;
			
			s.push({v, u});
		}
	}
}

int lca(int u, int v)
{
	if(lev[u] > lev[v])
		u ^= v ^= u ^= v;
	
	for(int i = LOGM-1; i >= 0; i--)
	{
		if(lev[v]-lev[u] >= (1 << i))
			v = par[i][v];
	}
	
	if(u == v)
		return u;
	
	for(int i = LOGM-1; i >= 0; i--)
	{
		if(par[i][u] != par[i][v])
		{
			u = par[i][u];
			v = par[i][v];
		}
	}
	
	return par[0][u];
}

int main()
{
	int n, k;
	std::cin >> n >> k;
	
	for(int i = 1; i < n; i++)
	{
		int a, b;
		std::cin >> a >> b;
		Adj[a].push_back(b);
		Adj[b].push_back(a);
	}
	
	s.push({1, 0});
	dfs();
	
	for(int i = 0; i <= k; i++)
		p[i] = -1;
	
	for(int i = 1; i <= n; i++)
	{
		int t;
		std::cin >> t;
		coll[t].push_back(i);
		type[i] = t;
		
		if(tar[t] == 0)
			tar[t] = i;
		else
			tar[t] = lca(tar[t], i);
	}
	
	for(int i = 0; i < k; i++)
	{
		ord[i] = {lev[tar[i+1]], i+1};
	}
	
	std::sort(ord, ord+k);
	
	for(int i = 0; i < k; i++)
	{
		int t = ord[i].second;
		if(mark[t])
			continue;
				q.push(t);
		mark[t] = i+1;
		while(!q.empty())
		{
			int c = q.front(); q.pop();
			for(int j : coll[c])
			{
				if(j == tar[t])
					continue;
				
				int v = type[par[0][j]];
				if(!mark[v])
				{
					mark[v] = i+1;
					q.push(v);
				}
				else if(mark[v] != i+1)
				{
					merge(i+1, mark[v]);
				}
			}
		}
	}
	
	int ans = 1;
	for(int i = 1; i <= n; i++)
	{
		for(int j : Adj[i])
			if(find(mark[type[i]]) != find(mark[type[j]]))
				deg[find(mark[type[i]])]++;
	}
	
	for(int i = 1; i <= k; i++)
		if(deg[i] == 1)
			ans++;
	
	std::cout << ans/2;
	std::cout << std::endl;
	
	return 0;
}

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