oj.uz

답안 #118362

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
118362 2019-06-18T18:26:14 Z raghav0307 Mergers (JOI19_mergers) C++14
0 / 100
 204 ms 66924 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];
set<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, -1, 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++){
		for(auto x: graph[i]){
			if(find(i) == find(x))	continue;
			degree[find(i)].insert(find(x));
		}
	}
	int ans = 0;
	for(int i = 1; i <= k; i++){
		if((int)degree[i].size() == 1)	ans++;
	}
	cout << (ans+1)/2 << "\n";
	return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 47352 KB Output is correct
2 Correct 44 ms 47352 KB Output is correct
3 Correct 46 ms 47352 KB Output is correct
4 Correct 43 ms 47352 KB Output is correct
5 Correct 72 ms 47484 KB Output is correct
6 Correct 44 ms 47352 KB Output is correct
7 Correct 47 ms 47352 KB Output is correct
8 Correct 43 ms 47352 KB Output is correct
9 Correct 44 ms 47352 KB Output is correct
10 Correct 45 ms 47352 KB Output is correct
11 Correct 43 ms 47352 KB Output is correct
12 Incorrect 43 ms 47352 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 47352 KB Output is correct
2 Correct 44 ms 47352 KB Output is correct
3 Correct 46 ms 47352 KB Output is correct
4 Correct 43 ms 47352 KB Output is correct
5 Correct 72 ms 47484 KB Output is correct
6 Correct 44 ms 47352 KB Output is correct
7 Correct 47 ms 47352 KB Output is correct
8 Correct 43 ms 47352 KB Output is correct
9 Correct 44 ms 47352 KB Output is correct
10 Correct 45 ms 47352 KB Output is correct
11 Correct 43 ms 47352 KB Output is correct
12 Incorrect 43 ms 47352 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 47352 KB Output is correct
2 Correct 44 ms 47352 KB Output is correct
3 Correct 46 ms 47352 KB Output is correct
4 Correct 43 ms 47352 KB Output is correct
5 Correct 72 ms 47484 KB Output is correct
6 Correct 44 ms 47352 KB Output is correct
7 Correct 47 ms 47352 KB Output is correct
8 Correct 43 ms 47352 KB Output is correct
9 Correct 44 ms 47352 KB Output is correct
10 Correct 45 ms 47352 KB Output is correct
11 Correct 43 ms 47352 KB Output is correct
12 Incorrect 43 ms 47352 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 55348 KB Output is correct
2 Correct 204 ms 66924 KB Output is correct
3 Incorrect 46 ms 47736 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 47352 KB Output is correct
2 Correct 44 ms 47352 KB Output is correct
3 Correct 46 ms 47352 KB Output is correct
4 Correct 43 ms 47352 KB Output is correct
5 Correct 72 ms 47484 KB Output is correct
6 Correct 44 ms 47352 KB Output is correct
7 Correct 47 ms 47352 KB Output is correct
8 Correct 43 ms 47352 KB Output is correct
9 Correct 44 ms 47352 KB Output is correct
10 Correct 45 ms 47352 KB Output is correct
11 Correct 43 ms 47352 KB Output is correct
12 Incorrect 43 ms 47352 KB Output isn't correct
13 Halted 0 ms 0 KB -