Submission #133237

#	Time	Username	Problem	Language	Result	Execution time	Memory
133237		hamzqq9	Mergers (JOI19_mergers)	C++14	100 / 100	2797 ms	158972 KiB

mergers

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define inf 2000000000000000
#define N 500005
#define MOD 998244353
#define KOK 700		
using namespace std;

int n,k,root,cnt;
int sub[N],has[N],h[N],dad[N],u[N],s[N],rem[N];
vector<int> v[N],v2[N];

void dfs6(int node,int ata) {

	for(int i:v2[node]) {

		if(i==ata) continue ;

		dfs6(i,node);

		rem[node]+=rem[i];

	}

	if(sz(v2[node])==1) {

		rem[node]=1;

		return ;

	}

	cnt+=rem[node]/2;

	rem[node]&=1;

}

int find(int x) {return dad[x]==x?x:(dad[x]=find(dad[x]));}

void merge(int x,int y) {

	while((x=find(x))!=find(root)) {

		dad[x]=find(u[x]);
		x=dad[x];

	}	

	while((y=find(y))!=find(root)) {

		dad[y]=find(u[y]);
		y=dad[y];

	}

}

void add(int node) {

	if(!has[s[node]]) has[s[node]]=node;
 
}

void ask(int node) {

	if(!has[s[node]]) return ;

	merge(has[s[node]],node);

}

void dfs5(int node,int ata) {

	has[s[node]]=0;

	for(int i:v[node]) {

		if(i==ata) continue ;

		dfs5(i,node);

	}

}

void dfs4(int node,int ata) {

	add(node);

	for(int i:v[node]) {

		if(i==ata) continue ;

		dfs4(i,node);

	}

}

void dfs3(int node,int ata) {

	ask(node);

	for(int i:v[node]) {

		if(i==ata) continue ;

		dfs3(i,node);

	}

}

void dfs2(int node,int ata,bool up) {

	for(int i:v[node]) {

		if(i==ata || i==h[node]) continue ;

		dfs2(i,node,0);

	}

	if(h[node]) dfs2(h[node],node,1);

	ask(root=node);
	add(root=node);

	for(int i:v[node]) {

		if(i==ata || i==h[node]) continue ;

		dfs3(i,node);
		dfs4(i,node);

	}

	if(!up) {

		dfs5(node,ata);

	}

}

void dfs(int node,int ata) {

	sub[node]=1;

	for(int i:v[node]) {

		if(i==ata) continue ;

		dfs(i,node);

		sub[node]+=sub[i];

		if(!h[node]) h[node]=i;
		else if(sub[i]>sub[h[node]]) h[node]=i;

	}

	u[node]=ata;dad[node]=node;

}

int main() {

	scanf("%d %d",&n,&k);

	for(int i=1;i<n;i++) {

		int x,y;

		scanf("%d %d",&x,&y);

		v[x].pb(y);
		v[y].pb(x);

	}

	for(int i=1;i<=n;i++) {

		scanf("%d",s+i);

	}

	dfs(1,0);
	dfs2(1,0,0);

	map<ii,int> pr;

	for(int i=1;i<=n;i++) {

		for(auto x:v[i]) {

			if(find(i)!=find(x) && !pr.count({find(i),find(x)})) {

				pr[{find(i),find(x)}]=pr[{find(x),find(i)}]=1;

				v2[find(i)].pb(find(x));
				v2[find(x)].pb(find(i));

			}

		}

	}

	dfs6(find(1),0);

	printf("%d",cnt+rem[find(1)]);
  	
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:180:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~
mergers.cpp:186:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~
mergers.cpp:195:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",s+i);
   ~~~~~^~~~~~~~~~

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