oj.uz

Submission #138092

# Submission time Handle Problem Language Result Execution time Memory
138092 2019-07-29T10:19:36 Z MohamedAhmed04 Mergers (JOI19_mergers) C++14
0 / 100
 139 ms 50504 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) ;
		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;
			}
			//cout<<node<<" : "<<nodenum[node]<<"\n";
			lowestdepth[state[node]] = min(lowestdepth[state[node]] , depth[lca[node]]) ;
			if(i == 0)
				continue;
			if(i == lowestdepth[state[node]])
			{
				if(id[state[P[node][0]]] == 0)
				{
					nodes++ ;
					id[state[P[node][0]]] = nodes ;
				}
				deg[id[state[P[node][0]]]]++ ;
				deg[id[state[node]]]++ ;
			}
			else
			{
				if(id[state[P[node][0]]] == 0)
					id[state[P[node][0]]] = id[state[node]] ; 
				lowestdepth[state[P[node][0]]] = lowestdepth[state[node]] ;
			    id[state[P[node][0]]] = id[state[node]] ;
			}
		}
	}
	//debugging
	if(nodes > n)
		while(1) ;
	int cnt = 0 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		if(deg[i] == 1)
			cnt++ ;
	}
	return cout<<(cnt+1)/2<<"\n" , 0 ;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35576 KB Output is correct
2 Correct 35 ms 35576 KB Output is correct
3 Correct 35 ms 35576 KB Output is correct
4 Correct 34 ms 35576 KB Output is correct
5 Correct 34 ms 35576 KB Output is correct
6 Correct 34 ms 35576 KB Output is correct
7 Correct 34 ms 35576 KB Output is correct
8 Correct 34 ms 35704 KB Output is correct
9 Correct 34 ms 35620 KB Output is correct
10 Correct 34 ms 35576 KB Output is correct
11 Correct 34 ms 35576 KB Output is correct
12 Correct 34 ms 35648 KB Output is correct
13 Incorrect 34 ms 35628 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35576 KB Output is correct
2 Correct 35 ms 35576 KB Output is correct
3 Correct 35 ms 35576 KB Output is correct
4 Correct 34 ms 35576 KB Output is correct
5 Correct 34 ms 35576 KB Output is correct
6 Correct 34 ms 35576 KB Output is correct
7 Correct 34 ms 35576 KB Output is correct
8 Correct 34 ms 35704 KB Output is correct
9 Correct 34 ms 35620 KB Output is correct
10 Correct 34 ms 35576 KB Output is correct
11 Correct 34 ms 35576 KB Output is correct
12 Correct 34 ms 35648 KB Output is correct
13 Incorrect 34 ms 35628 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35576 KB Output is correct
2 Correct 35 ms 35576 KB Output is correct
3 Correct 35 ms 35576 KB Output is correct
4 Correct 34 ms 35576 KB Output is correct
5 Correct 34 ms 35576 KB Output is correct
6 Correct 34 ms 35576 KB Output is correct
7 Correct 34 ms 35576 KB Output is correct
8 Correct 34 ms 35704 KB Output is correct
9 Correct 34 ms 35620 KB Output is correct
10 Correct 34 ms 35576 KB Output is correct
11 Correct 34 ms 35576 KB Output is correct
12 Correct 34 ms 35648 KB Output is correct
13 Incorrect 34 ms 35628 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 50504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35576 KB Output is correct
2 Correct 35 ms 35576 KB Output is correct
3 Correct 35 ms 35576 KB Output is correct
4 Correct 34 ms 35576 KB Output is correct
5 Correct 34 ms 35576 KB Output is correct
6 Correct 34 ms 35576 KB Output is correct
7 Correct 34 ms 35576 KB Output is correct
8 Correct 34 ms 35704 KB Output is correct
9 Correct 34 ms 35620 KB Output is correct
10 Correct 34 ms 35576 KB Output is correct
11 Correct 34 ms 35576 KB Output is correct
12 Correct 34 ms 35648 KB Output is correct
13 Incorrect 34 ms 35628 KB Output isn't correct
14 Halted 0 ms 0 KB -