oj.uz

Submission #118317

# Submission time Handle Problem Language Result Execution time Memory
118317 2019-06-18T16:06:50 Z raghav0307 Mergers (JOI19_mergers) C++14
0 / 100
 96 ms 35820 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, -1, 0);
	for(int i = 1; i <= n; i++)	color[i] = i;
	for(int i = 1; i <= k; i++){
		for(int j = 1; j < 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)]++;
		}
	}
	int ans = 0;
	for(int i = 1; i <= k; i++){
		if(degree[i] == 1)	ans++;
	}
	cout << (ans+1)/2 << "\n";
	return 0;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 1; j < state[i].size(); j++){
                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 22 ms 23936 KB Output is correct
3 Correct 22 ms 23808 KB Output is correct
4 Correct 22 ms 23808 KB Output is correct
5 Correct 22 ms 23888 KB Output is correct
6 Correct 22 ms 23936 KB Output is correct
7 Correct 22 ms 23808 KB Output is correct
8 Correct 22 ms 23936 KB Output is correct
9 Correct 22 ms 23808 KB Output is correct
10 Correct 25 ms 23808 KB Output is correct
11 Correct 24 ms 23928 KB Output is correct
12 Incorrect 23 ms 23808 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 22 ms 23936 KB Output is correct
3 Correct 22 ms 23808 KB Output is correct
4 Correct 22 ms 23808 KB Output is correct
5 Correct 22 ms 23888 KB Output is correct
6 Correct 22 ms 23936 KB Output is correct
7 Correct 22 ms 23808 KB Output is correct
8 Correct 22 ms 23936 KB Output is correct
9 Correct 22 ms 23808 KB Output is correct
10 Correct 25 ms 23808 KB Output is correct
11 Correct 24 ms 23928 KB Output is correct
12 Incorrect 23 ms 23808 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 22 ms 23936 KB Output is correct
3 Correct 22 ms 23808 KB Output is correct
4 Correct 22 ms 23808 KB Output is correct
5 Correct 22 ms 23888 KB Output is correct
6 Correct 22 ms 23936 KB Output is correct
7 Correct 22 ms 23808 KB Output is correct
8 Correct 22 ms 23936 KB Output is correct
9 Correct 22 ms 23808 KB Output is correct
10 Correct 25 ms 23808 KB Output is correct
11 Correct 24 ms 23928 KB Output is correct
12 Incorrect 23 ms 23808 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 32640 KB Output is correct
2 Correct 96 ms 35820 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

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 22 ms 23936 KB Output is correct
3 Correct 22 ms 23808 KB Output is correct
4 Correct 22 ms 23808 KB Output is correct
5 Correct 22 ms 23888 KB Output is correct
6 Correct 22 ms 23936 KB Output is correct
7 Correct 22 ms 23808 KB Output is correct
8 Correct 22 ms 23936 KB Output is correct
9 Correct 22 ms 23808 KB Output is correct
10 Correct 25 ms 23808 KB Output is correct
11 Correct 24 ms 23928 KB Output is correct
12 Incorrect 23 ms 23808 KB Output isn't correct
13 Halted 0 ms 0 KB -