Submission #1146367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146367		SmuggingSpun	Mergers (JOI19_mergers)	C++20	0 / 100	44 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>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){
	if(min_sub[s] >= low[s] && max_sub[s] <= tail[s]){
		return true;
	}
	for(int& d : g[s]){
		if(d != parent[s] && dfs_3(d)){
			return true;
		}
	}
	return false;
}
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 cnt = 0;
	for(int i = 2; i <= n; i++){
		if(!vis.test(i) && vis.test(parent[i]) && dfs_3(i)){
			cnt++;
		}
	}
	cout << ((cnt + 1) >> 1);
}

Compilation message (stderr)

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