oj.uz

답안 #118498

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
118498 2019-06-19T05:58:50 Z raghav0307 Mergers (JOI19_mergers) C++14
0 / 100
 91 ms 35788 KB 
/*raghav0307 - Raghav Gupta*/

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
#define int ll
const int MAXN = 5e5 + 5;

vector<int> graph[MAXN];
vector<int> state[MAXN];

int depth[MAXN];
int parent[MAXN];
int degree[MAXN];

void dfs(int nd, int p, int lvl){
	parent[nd] = p;
	depth[nd] = lvl;
	for(auto x: graph[nd]){
		if(x == p)	continue;
		dfs(x, nd, lvl+1);
	}
}

int color[MAXN];

int find(int x){
	return color[x] == x ? x : color[x] = find(color[x]);
}

void Union(int a, int b){
	if(a == b)	return;
	a = find(a);
	b = find(b);
	while(a != b){
		if(depth[b] > depth[a])
			swap(a, b);
		int x = find(parent[a]);
		color[a] = x;
		a = x;
	}
}

signed main(){
	fast_io();
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < n-1; i++){
		int a, b;
		cin >> a >> b;
		graph[a].pb(b);
		graph[b].pb(a);
	}
	for(int i = 1; i <= n; i++){
		int indx;	cin >> indx;
		state[indx].pb(i);
	}
	dfs(1, 0, 0);
	for(int i = 1; i <= n; i++)	color[i] = i;
	for(int i = 1; i <= k; i++){
		for(int j = 1; j < (int)state[i].size(); j++){
			Union(state[i][j], state[i][j-1]);
		}
	}
	for(int i = 1; i <= n; i++){
		if(find(i) != i)	continue;
		if(find(parent[i]) == 0)	continue;
		degree[i]++;
		degree[find(parent[i])]++;
	}
	int ans = 0;
	for(int i = 1; i <= k; i++){
		// cout << i << "'s degree " << degree[i] << "\n";
		if(degree[i] == 1)	ans++;
	}
	// cout << ans << "\n";
	cout << (ans+1)/2 << "\n";
	return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 23808 KB Output is correct
2 Correct 21 ms 23936 KB Output is correct
3 Correct 21 ms 23936 KB Output is correct
4 Correct 21 ms 23808 KB Output is correct
5 Correct 22 ms 23808 KB Output is correct
6 Correct 21 ms 23808 KB Output is correct
7 Correct 21 ms 23808 KB Output is correct
8 Correct 22 ms 23808 KB Output is correct
9 Correct 21 ms 23808 KB Output is correct
10 Correct 22 ms 23880 KB Output is correct
11 Correct 21 ms 23856 KB Output is correct
12 Incorrect 21 ms 23936 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 23808 KB Output is correct
2 Correct 21 ms 23936 KB Output is correct
3 Correct 21 ms 23936 KB Output is correct
4 Correct 21 ms 23808 KB Output is correct
5 Correct 22 ms 23808 KB Output is correct
6 Correct 21 ms 23808 KB Output is correct
7 Correct 21 ms 23808 KB Output is correct
8 Correct 22 ms 23808 KB Output is correct
9 Correct 21 ms 23808 KB Output is correct
10 Correct 22 ms 23880 KB Output is correct
11 Correct 21 ms 23856 KB Output is correct
12 Incorrect 21 ms 23936 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 23808 KB Output is correct
2 Correct 21 ms 23936 KB Output is correct
3 Correct 21 ms 23936 KB Output is correct
4 Correct 21 ms 23808 KB Output is correct
5 Correct 22 ms 23808 KB Output is correct
6 Correct 21 ms 23808 KB Output is correct
7 Correct 21 ms 23808 KB Output is correct
8 Correct 22 ms 23808 KB Output is correct
9 Correct 21 ms 23808 KB Output is correct
10 Correct 22 ms 23880 KB Output is correct
11 Correct 21 ms 23856 KB Output is correct
12 Incorrect 21 ms 23936 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 31156 KB Output is correct
2 Correct 91 ms 35788 KB Output is correct
3 Incorrect 24 ms 24192 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 23808 KB Output is correct
2 Correct 21 ms 23936 KB Output is correct
3 Correct 21 ms 23936 KB Output is correct
4 Correct 21 ms 23808 KB Output is correct
5 Correct 22 ms 23808 KB Output is correct
6 Correct 21 ms 23808 KB Output is correct
7 Correct 21 ms 23808 KB Output is correct
8 Correct 22 ms 23808 KB Output is correct
9 Correct 21 ms 23808 KB Output is correct
10 Correct 22 ms 23880 KB Output is correct
11 Correct 21 ms 23856 KB Output is correct
12 Incorrect 21 ms 23936 KB Output isn't correct
13 Halted 0 ms 0 KB -