Submission #1146382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146382		SmuggingSpun	Mergers (JOI19_mergers)	C++20	0 / 100	60 ms	35264 KiB

mergers

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
const int lim = 5e5 + 5;
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
int n, k, time_dfs = 0, parent[lim], min_color[lim], max_color[lim], min_sub[lim], max_sub[lim], low[lim], tail[lim], color[lim];
bitset<lim>used, vis;
vector<int>cnt, g[lim], vertex[lim];
void dfs_1(int s){
	low[s] = max_color[color[s]] = ++time_dfs;
	if(min_color[color[s]] == -1){
		min_color[color[s]] = time_dfs;
	}
	for(int& d : g[s]){
		if(d != parent[s]){
			parent[d] = s;
			dfs_1(d);
		}
	}
	tail[s] = time_dfs;
}
void dfs_2(int s){
	min_sub[s] = min_color[color[s]];
	max_sub[s] = max_color[color[s]];
	for(int& d : g[s]){
		if(d != parent[s]){
			dfs_2(d);
			minimize(min_sub[s], min_sub[d]);
			maximize(max_sub[s], max_sub[d]);
		}
	}
}
bool dfs_3(int s){
	bool have_child = false;
	for(int& d : g[s]){
		if(d != parent[s] && dfs_3(d)){
			have_child = true;
		}
	}
	if(!have_child && min_sub[s] >= low[s] && max_sub[s] <= tail[s]){
		cnt.back()++;
		return true;
	}
	return have_child;
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> k;
	for(int i = 1; i < n; i++){
		int u, v;
		cin >> u >> v;
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}
	for(int i = 1; i <= n; i++){
		cin >> color[i];
		vertex[color[i]].emplace_back(i);
	}
	memset(min_color, -1, sizeof(min_color));
	dfs_1(parent[1] = 1);
	dfs_2(1);
	queue<int>q;
	q.push(color[1]);
	used.reset();
	vis.reset();
	used.set(color[1]);
	vis.set(1);
	while(!q.empty()){
		int pat_color = q.front();
		q.pop();
		for(int& u : vertex[pat_color]){
			while(!vis.test(u)){
				vis.set(u);
				if(!used.test(color[u])){
					used.set(color[u]);
					q.push(color[u]);
				}
				u = parent[u];
			}
		}
	}
	int sum_cnt = 0;
	for(int i = 2; i <= n; i++){
		if(!vis.test(i) && vis.test(parent[i])){
			cnt.emplace_back(0);
			dfs_3(i);
			sum_cnt += cnt.back();
		}
	}
	if(cnt.empty()){
		return cout << 0, 0;
	}
	sort(cnt.begin(), cnt.end(), greater<int>());
	cout << (cnt[0] <= (sum_cnt -= cnt[0]) ? ((sum_cnt + cnt[0] + 1) >> 1) : cnt[0]);
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:58:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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