Submission #105105

#	Time	Username	Problem	Language	Result	Execution time	Memory
105105		antimirage	Mergers (JOI19_mergers)	C++14	100 / 100	1806 ms	136192 KiB

mergers

#include <bits/stdc++.h>
 
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
 
using namespace std;
 
const int N = 5e5 + 5;
 
int n, k, x, y, tin[N], tout[N], timer, up[N][21], pref[N], par[N], ans, m[N], sz[N], deg[N];
 
vector < vector <int> > g, vec;
 
void dfs (int v, int p = 0)
{
	par[v] = p;
	tin[v] = ++timer;
	
	up[v][0] = p;
	for (int i = 1; i < 20; i++)
		up[v][i] = up[ up[v][i - 1] ][i - 1];
		
	for (auto to : g[v]){
		if (to == p) continue;
		dfs(to, v);
	}
	tout[v] = ++timer;
}
bool upper (int a, int b)
{
	return tin[a] <= tin[b] && tout[b] <= tout[a];
}
int lca (int a, int b)
{
	if (upper(a, b) ) return a;
	if (upper(b, a) ) return b;
		
	for (int i = 19; i >= 0; i--){
		if (up[a][i] && !upper(up[a][i], b) )
			a = up[a][i];
	}
	return up[a][0];
}
int get (int v){
	return v == m[v] ? v : m[v] = get(m[v]);
}
void unite (int a, int b)
{
	a = get(a);
	b = get(b);
	if (a != b){
		if (sz[a] > sz[b]) swap(a, b);
		
		sz[b] += sz[a];
		m[a] = b;
		deg[b] += deg[a];
	}
}
void Dfs (int v, int p = 0)
{
	for (auto to : g[v]){
		
		if (to == p) continue;
		Dfs(to, v);
		
		pref[v] += pref[to];
	}
	if (pref[v] > 0 && p){
		unite(v, p);
	}
	else if (p) {
		++deg[get(p)];
		++deg[get(v)];
	}
}
main(){
	
	cin >> n >> k;
	g.resize(n + 1);
	vec.resize(k + 1);
	
	for (int i = 1; i < n; i++){
		
		scanf("%d%d", &x, &y);
		g[x].pb(y);
		g[y].pb(x);
	}
	dfs(1);	
	
	for (int i = 1; i <= n; i++){
		scanf("%d", &x);
		vec[x].pb(i);
		
		m[i] = i;
		sz[i] = 1;
	}
	
	for (int i = 1; i <= k; i++){
		if (vec[i].empty() ) continue;
		
		int LCA = vec[i][0];
		
		for (int j = 1; j < (int)vec[i].size(); j++){
			LCA = lca(LCA, vec[i][j]);
		}
		for (int j = 0; j < (int)vec[i].size(); j++){
			pref[ vec[i][j] ]++;
			pref[ LCA ]--;
		}
	}
	
	Dfs(1);
	
	for (int i = 1; i <= n; i++){
		if (m[i] == i && deg[i] == 1)
			ans++;
	}
	if (sz[ get(1) ] == n){
		puts("0");
	}
	else{
		cout << (ans + 1) / 2 << endl;
	}
}
/**
5 4
1 2
2 3
2 4
2 5
4
1
2
3
4
5
2


**/

Compilation message (stderr)

mergers.cpp:79:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
mergers.cpp: In function 'int main()':
mergers.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30