Submission #412010

#	Time	Username	Problem	Language	Result	Execution time	Memory
412010		faresbasbs	Mergers (JOI19_mergers)	C++14	100 / 100	2399 ms	104576 KiB

mergers

#include <bits/stdc++.h>
using namespace std;
int n,k,t,cnt=1,deg[500001],color[500001],ent[500001],out[500001],mn[500001],mx[500001],par[500001];
vector<int> segmn,segmx,graph[500001];
set<pair<int,int>> st;

void dfs(int curr , int p){
	ent[curr] = cnt++;
	for(auto i : graph[curr]){
		if(i == p){
			continue;
		}
		par[i] = curr;
		dfs(i,curr);
	}
	out[curr] = cnt-1;
}

void dfs2(int curr , int p , int rt){
	// cout << curr << " " << p << " " << rt << endl;
	for(auto i : graph[curr]){
		if(i == p){
			continue;
		}
		if(st.count({curr,i})){
			deg[rt] += 1 , deg[cnt+1] += 1;
			dfs2(i,curr,++cnt);
		}else{
			dfs2(i,curr,rt);
		}
	}
}

int getmax(int a , int b , int curr , int l , int r){
	if(b < l || a > r){
		return 0;
	}
	if(a <= l && b >= r){
		return segmx[curr];
	}
	int mid = (l+r)/2;
	return max(getmax(a,b,2*curr,l,mid),getmax(a,b,2*curr+1,mid+1,r));
}

int getmin(int a , int b , int curr , int l , int r){
	if(b < l || a > r){
		return 1000000;
	}
	if(a <= l && b >= r){
		return segmn[curr];
	}
	int mid = (l+r)/2;
	return min(getmin(a,b,2*curr,l,mid),getmin(a,b,2*curr+1,mid+1,r));
}

void upd(int curr , int v1 , int v2){
	while(curr){
		segmn[curr] = min(segmn[curr],v1);
		segmx[curr] = max(segmx[curr],v2);
		curr /= 2;
	}
}

int main(){
	cin >> n >> k;
	t = pow(2,ceil(log2(n)));
	segmn.resize(2*t,1000000),segmx.resize(2*t,0);
	for(int i = 0 ; i < n-1 ; i += 1){
		int a,b;
		cin >> a >> b;
		graph[a].push_back(b),graph[b].push_back(a);
	}
	for(int i = 1 ; i <= k ; i += 1){
		mn[i] = 1000000 , mx[i] = 0;
	}
	for(int i = 1 ; i <= n ; i += 1){
		cin >> color[i];
	}
	dfs(1,1);
	for(int i = 1 ; i <= n ; i += 1){
		mn[color[i]] = min(mn[color[i]],ent[i]);
		mx[color[i]] = max(mx[color[i]],ent[i]);
	}
	for(int i = 1 ; i <= n ; i += 1){
		upd(ent[i]+t-1,mn[color[i]],mx[color[i]]);
	}
	for(int i = 2 ; i <= n ; i += 1){
		if(getmin(ent[i],out[i],1,1,t) >= ent[i] && getmax(ent[i],out[i],1,1,t) <= out[i]){
			st.insert({par[i],i});
		}
	}
	cnt = 1;
	dfs2(1,1,1);
	int num = 0;
	for(int i = 1 ; i <= cnt ; i += 1){
		if(deg[i] == 1){
			num += 1;
		}
	}
	cout << (num+1)/2 << endl;
}

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