Submission #1146395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146395		SmuggingSpun	Mergers (JOI19_mergers)	C++20	0 / 100	61 ms	35260 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_4(int s){
	bool have_child = false;
	for(int& d : g[s]){
		if(d != parent[s] && dfs_4(d)){
			have_child = true;
		}
	}
	if(!have_child && min_sub[s] >= low[s] && max_sub[s] <= tail[s]){
		cnt.back()++;
		return true;
	}
	return have_child;
}
void dfs_3(int s){
	if(min_sub[s] >= low[s] && max_sub[s] <= tail[s]){
		cnt.emplace_back(0);
		dfs_4(s);
		return;
	}
	for(int& d : g[s]){
		if(d != parent[s]){
			dfs_3(d);
		}
	}
}
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[2] = 2);
	dfs_2(2);
	queue<int>q;
	q.push(color[2]);
	used.reset();
	vis.reset();
	used.set(color[2]);
	vis.set(2);
	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];
			}
		}
	}
	for(int i = 1; i <= n; i++){
		if(!vis.test(i) && vis.test(parent[i])){
			dfs_3(i);
		}
	}
	if(cnt.empty()){
		return cout << 0, 0;
	}
	int sum_cnt = accumulate(cnt.begin(), cnt.end(), 0), max_cnt = *max_element(cnt.begin(), cnt.end());
	cout << (max_cnt <= (sum_cnt -= max_cnt) ? ((sum_cnt + max_cnt + 1) >> 1) : max_cnt);
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:70:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |                 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