oj.uz

Submission #138084

# Submission time Handle Problem Language Result Execution time Memory
138084 2019-07-29T09:57:53 Z MohamedAhmed04 Mergers (JOI19_mergers) C++14
0 / 100
 180 ms 54400 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 5e5 + 5 ;

vector< vector<int> >adj(MAX) ;
vector< vector<int> >st(MAX) ;
vector< vector<int> >level(MAX) ;
int n , k;

int state[MAX] , P[MAX][22] , depth[MAX] , lca[MAX];
int lowestdepth[MAX] , nodenum[MAX] , deg[MAX] , id[MAX];
int nodes = 0 ;

void dfs(int node , int lvl , int par)
{
	depth[node] = lvl ;
	P[node][0] = par ;
	for(auto &child : adj[node])
	{
		if(child == par)
			continue ;
		dfs(child , lvl + 1 , node) ;
	}
	return ;
}

void preprocess()
{
	dfs(1 , 0 , 0) ;
	for(int j = 1 ; j < 22 ; ++j)
	{
		for(int i = 1 ; i <= n ; ++i)
			P[i][j] = P[P[i][j-1]][j-1] ;
	}
	return ;
}

int LCA(int x , int y)
{
	if(depth[x] < depth[y])
		swap(x , y) ;
	for(int i = 21 ; i >= 0 ; --i)
	{
		if(depth[x] - (1 << i) >= depth[y])
			x = P[x][i] ;
	}
	if(x == y)
		return x ;
	for(int i = 21 ; i >= 0 ; --i)
	{
		if(P[x][i] != P[y][i])
			x = P[x][i] , y = P[y][i] ;
	}
	return P[x][0] ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>k ;
	for(int i = 0 ; i < n-1 ; ++i)
	{
		int x , y ;
		cin>>x>>y ;
		adj[x].push_back(y) ;
		adj[y].push_back(x) ;
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		cin>>state[i] ;
		st[state[i]].push_back(i) ;
	}
	preprocess() ;
	for(int i = 1 ; i <= k ; ++i)
	{
		int lca2 = st[i][0] ;
		for(auto &node : st[i])
			lca2 = LCA(lca2 , node) ;
		lca2 = P[lca2][0] ;
		for(auto &node : st[i])
		{
			lca[node] = lca2 ;
		}
	}
	int maxdepth = 0 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		level[depth[i]].push_back(i) ;
		maxdepth = max(maxdepth , depth[i]) ;
		lowestdepth[i] = 1e9 ;
	}
	depth[0] = -1 ;
	for(int i = maxdepth ; i >= 0 ; --i)
	{
		for(auto &node : level[i])
		{
			if(id[state[node]] == 0)
			{
				nodes++ ;
				id[state[node]] = nodes;
			}
			nodenum[node] = id[state[node]] ;
			//cout<<node<<" : "<<nodenum[node]<<"\n";
			lowestdepth[node] = min(lowestdepth[node] , depth[lca[node]]) ;
			if(i == 0)
				continue;
			if(i-1 == lowestdepth[node])
			{
				if(id[state[P[node][0]]] == 0)
				{
					nodes++ ;
					id[state[P[node][0]]] = nodes ;
					nodenum[P[node][0]] = id[state[P[node][0]]] ;
				}
				deg[nodenum[P[node][0]]]++ ;
				deg[nodenum[node]]++ ;
			}
			else
			{
				if(id[state[P[node][0]]] == 0)
				{
					id[state[P[node][0]]] = id[state[node]] ;
					nodenum[P[node][0]] = nodenum[node] ; 
				}
				lowestdepth[P[node][0]] = lowestdepth[node] ;
				nodenum[P[node][0]] = nodenum[node] ;
			}
		}
	}
	int cnt = 0 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		if(deg[i] == 1)
			cnt++ ;
	}
	if(cnt == 1)
		cnt = 0 ;
	return cout<<(cnt+1)/2<<"\n" , 0 ;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 35576 KB Output is correct
2 Incorrect 42 ms 35704 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 35576 KB Output is correct
2 Incorrect 42 ms 35704 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 35576 KB Output is correct
2 Incorrect 42 ms 35704 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 50808 KB Output is correct
2 Correct 180 ms 54400 KB Output is correct
3 Incorrect 42 ms 36244 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 35576 KB Output is correct
2 Incorrect 42 ms 35704 KB Output isn't correct
3 Halted 0 ms 0 KB -