oj.uz

Submission #138061

# Submission time Handle Problem Language Result Execution time Memory
138061 2019-07-29T08:59:38 Z anayk Mergers (JOI19_mergers) C++14
0 / 100
 903 ms 262148 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>

#define MAXN 500005
#define LOGM 22

int par[LOGM][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<int> s;
int deg[MAXN];

void dfs()
{
	while(!s.empty())
	{
		int u = s.top(); s.pop();
		int p;
		if(s.empty())
			p = 0;
		else
			p = s.top();
		
		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]];
		}
		
		for(int v : Adj[u])
		{
			if(v == p)
				continue;
			
			s.push(v);
		}
	}
}

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);
	dfs();
	
	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);
				}
			}
		}
	}
	
	int ans = 1;
	for(int i = 1; i <= n; i++)
	{
		for(int j : Adj[i])
			if(mark[type[i]] != mark[type[j]])
				deg[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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 903 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 903 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 903 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 426 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 903 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -