oj.uz

Submission #138098

# Submission time Handle Problem Language Result Execution time Memory
138098 2019-07-29T10:42:59 Z MohamedAhmed04 Mergers (JOI19_mergers) C++14
0 / 100
 226 ms 50416 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<<" : "<<id[state[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)
					lowestdepth[state[node]] = min(lowestdepth[state[node]] , lowestdepth[state[P[node][0]]]) ;
				else
					lowestdepth[state[P[node][0]]] = lowestdepth[state[node]] ;
			    id[state[P[node][0]]] = id[state[node]] ;
			}
		}
	}
	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 35552 KB Output is correct
3 Correct 35 ms 35576 KB Output is correct
4 Correct 35 ms 35576 KB Output is correct
5 Correct 42 ms 35448 KB Output is correct
6 Correct 35 ms 35668 KB Output is correct
7 Correct 39 ms 35564 KB Output is correct
8 Correct 35 ms 35576 KB Output is correct
9 Correct 42 ms 35576 KB Output is correct
10 Correct 38 ms 35704 KB Output is correct
11 Correct 36 ms 35576 KB Output is correct
12 Correct 35 ms 35548 KB Output is correct
13 Incorrect 35 ms 35576 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 35552 KB Output is correct
3 Correct 35 ms 35576 KB Output is correct
4 Correct 35 ms 35576 KB Output is correct
5 Correct 42 ms 35448 KB Output is correct
6 Correct 35 ms 35668 KB Output is correct
7 Correct 39 ms 35564 KB Output is correct
8 Correct 35 ms 35576 KB Output is correct
9 Correct 42 ms 35576 KB Output is correct
10 Correct 38 ms 35704 KB Output is correct
11 Correct 36 ms 35576 KB Output is correct
12 Correct 35 ms 35548 KB Output is correct
13 Incorrect 35 ms 35576 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 35552 KB Output is correct
3 Correct 35 ms 35576 KB Output is correct
4 Correct 35 ms 35576 KB Output is correct
5 Correct 42 ms 35448 KB Output is correct
6 Correct 35 ms 35668 KB Output is correct
7 Correct 39 ms 35564 KB Output is correct
8 Correct 35 ms 35576 KB Output is correct
9 Correct 42 ms 35576 KB Output is correct
10 Correct 38 ms 35704 KB Output is correct
11 Correct 36 ms 35576 KB Output is correct
12 Correct 35 ms 35548 KB Output is correct
13 Incorrect 35 ms 35576 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 226 ms 50416 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 35552 KB Output is correct
3 Correct 35 ms 35576 KB Output is correct
4 Correct 35 ms 35576 KB Output is correct
5 Correct 42 ms 35448 KB Output is correct
6 Correct 35 ms 35668 KB Output is correct
7 Correct 39 ms 35564 KB Output is correct
8 Correct 35 ms 35576 KB Output is correct
9 Correct 42 ms 35576 KB Output is correct
10 Correct 38 ms 35704 KB Output is correct
11 Correct 36 ms 35576 KB Output is correct
12 Correct 35 ms 35548 KB Output is correct
13 Incorrect 35 ms 35576 KB Output isn't correct
14 Halted 0 ms 0 KB -