Submission #772747

#	Time	Username	Problem	Language	Result	Execution time	Memory
772747		Mohammad_Parsa	Mergers (JOI19_mergers)	C++17	34 / 100	3079 ms	31272 KiB

mergers

/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb push_back
#define F first
#define S second
#define mk make_pair
typedef long long ll;

const int N=5e5+7;
int n,k,st[N],fn[N],t,s[N],mark[N],sum[N],ans;
vector<int>vec[N],ver[N];

void dfs1(int v=1,int p=0){
	st[v]=t++;
	for(auto u:vec[v]){
		if(u!=p) dfs1(u,v);
	}
	fn[v]=t++;
}

void dfs2(int v=1,int p=0){
	sum[v]=mark[v];
	for(auto u:vec[v]){
		if(u==p)continue;
		mark[u]=1;
		for(int i=1;i<=k;i++){
			int x=0,y=0;
			for(auto w:ver[i]){
				if(st[w]>=st[u] && fn[w]<=fn[u])x++;
				else y++;
			}
			if(x&&y)mark[u]=0;
		}
		dfs2(u,v);
		sum[v]+=sum[u];
	}
}

void dfs3(int v=1,int p=0){
	if(mark[v] && (sum[v]==1 || sum[v]==sum[1]))ans++;
	for(auto u:vec[v]){
		if(u==p)continue;
		dfs3(u,v);
	}
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	int u,v;
	for(int i=0;i<n-1;i++){
		cin>>u>>v;
		vec[u].pb(v);
		vec[v].pb(u);
	}
	for(int i=1;i<=n;i++){
		cin>>s[i];
		ver[s[i]].pb(i);
	}
	dfs1();
	dfs2();
	dfs3();
	cout<<ans/2+(ans%2==1);
}

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