oj.uz

답안 #138089

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
138089 2019-07-29T10:10:17 Z MohamedAhmed04 Mergers (JOI19_mergers) C++14
0 / 100
 129 ms 50544 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;
			}
			//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 ;
				}
				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[P[node][0]] = lowestdepth[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

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 35576 KB Output is correct
2 Correct 41 ms 35576 KB Output is correct
3 Correct 40 ms 35576 KB Output is correct
4 Correct 42 ms 35576 KB Output is correct
5 Correct 34 ms 35576 KB Output is correct
6 Correct 35 ms 35704 KB Output is correct
7 Correct 41 ms 35576 KB Output is correct
8 Correct 39 ms 35576 KB Output is correct
9 Correct 35 ms 35704 KB Output is correct
10 Correct 35 ms 35576 KB Output is correct
11 Correct 34 ms 35592 KB Output is correct
12 Correct 35 ms 35580 KB Output is correct
13 Incorrect 34 ms 35576 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 35576 KB Output is correct
2 Correct 41 ms 35576 KB Output is correct
3 Correct 40 ms 35576 KB Output is correct
4 Correct 42 ms 35576 KB Output is correct
5 Correct 34 ms 35576 KB Output is correct
6 Correct 35 ms 35704 KB Output is correct
7 Correct 41 ms 35576 KB Output is correct
8 Correct 39 ms 35576 KB Output is correct
9 Correct 35 ms 35704 KB Output is correct
10 Correct 35 ms 35576 KB Output is correct
11 Correct 34 ms 35592 KB Output is correct
12 Correct 35 ms 35580 KB Output is correct
13 Incorrect 34 ms 35576 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 35576 KB Output is correct
2 Correct 41 ms 35576 KB Output is correct
3 Correct 40 ms 35576 KB Output is correct
4 Correct 42 ms 35576 KB Output is correct
5 Correct 34 ms 35576 KB Output is correct
6 Correct 35 ms 35704 KB Output is correct
7 Correct 41 ms 35576 KB Output is correct
8 Correct 39 ms 35576 KB Output is correct
9 Correct 35 ms 35704 KB Output is correct
10 Correct 35 ms 35576 KB Output is correct
11 Correct 34 ms 35592 KB Output is correct
12 Correct 35 ms 35580 KB Output is correct
13 Incorrect 34 ms 35576 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 129 ms 50544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 35576 KB Output is correct
2 Correct 41 ms 35576 KB Output is correct
3 Correct 40 ms 35576 KB Output is correct
4 Correct 42 ms 35576 KB Output is correct
5 Correct 34 ms 35576 KB Output is correct
6 Correct 35 ms 35704 KB Output is correct
7 Correct 41 ms 35576 KB Output is correct
8 Correct 39 ms 35576 KB Output is correct
9 Correct 35 ms 35704 KB Output is correct
10 Correct 35 ms 35576 KB Output is correct
11 Correct 34 ms 35592 KB Output is correct
12 Correct 35 ms 35580 KB Output is correct
13 Incorrect 34 ms 35576 KB Output isn't correct
14 Halted 0 ms 0 KB -