Submission #604445

#	Time	Username	Problem	Language	Result	Execution time	Memory
604445		juggernaut	Mergers (JOI19_mergers)	C++14	100 / 100	1696 ms	176640 KiB

mergers

#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
int n,k;
vector<int>g[500005];
int sz[500005];
int gp[500005];
set<int>st[500005];
int pivot[500005];
int sub[500005];
void add(int a,int b){
	if(st[a].size()<st[b].size()){
		swap(st[a],st[b]);
		swap(pivot[a],pivot[b]);
	}
	for(int to:st[b]){
		if(!st[a].count(to)){
			st[a].insert(to);
			pivot[a]+=sz[to];
		}
	}
	st[b].clear();
}
int tot;
int sweet[500005];
map<int,int>mp[500005];
void dfs(int v,int p){
	pivot[v]=sz[gp[v]];
	sub[v]=1;
	st[v].insert(gp[v]);
	for(int to:g[v])if(to^p){
		dfs(to,v);
		if(sub[to]==pivot[to]){
			mp[v][to]=true;
			sweet[v]++;
			tot++;
		}
		sweet[v]+=sweet[to];
		add(v,to);
		sub[v]+=sub[to];
	}
}
int ans;
void go(int v,int p){
	for(int to:g[v])if(to^p){
		go(to,v);
		if(mp[v][to]){
			if(sweet[to]>0&&tot-sweet[to]-1>0){
				ans--;
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i^n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&gp[i]);
		sz[gp[i]]++;
	}
	dfs(1,1);
	ans=tot;
	go(1,1);
	cout<<(ans+1>>1);
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:79:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |  cout<<(ans+1>>1);
      |         ~~~^~
mergers.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d%d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~
mergers.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~
mergers.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   scanf("%d",&gp[i]);
      |   ~~~~~^~~~~~~~~~~~~

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