Submission #332587

#	Time	Username	Problem	Language	Result	Execution time	Memory
332587		CaroLinda	Mergers (JOI19_mergers)	C++14	100 / 100	1231 ms	98524 KiB

mergers

#include <bits/stdc++.h>

#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
#define ll long long

const int MAXN = 5e5+10 ;

using namespace std ;

int n , k ;
int state[MAXN] , deg[MAXN] ;
int dsu[MAXN] , qtdState[MAXN] ;
vector<int> adj[MAXN] ;
map<int,int> *ptr[MAXN] ;


int find(int x) 
{
	if(x == dsu[x] ) return x ;
	return dsu[x] = find(dsu[x] ) ;
}

void join(int x, int y )
{
	x = find(x) ;
	y = find(y) ;

	if(x  == y ) return ;

	if(rand() % 2 ) swap(x,y) ;

	deg[x] += deg[y] ;
	dsu[y] = x ;

}

int dfs(int x, int father)
{
	int bc = -1 ;
	int subBc = 0 ;
	int sub = 1 ;

	for(auto e : adj[x] )
	{

		if(e == father ) continue ;

		int subChild = dfs(e,x) ;
		sub += subChild ;

		if(subChild > subBc )
		{
			subBc = subChild ;
			bc = e ;			
		}

	}

	if(bc == -1 ) ptr[x] = new map<int,int> ;
	else ptr[x] = ptr[bc] ;

	if( sz( (*ptr[x]) ) == 0 && bc != -1 )
	{
		deg[ find(bc) ]++ ;
		deg[ find(x) ]++ ;
	}
	else if(bc != -1 ) join(x, bc) ;

	for(auto e : adj[x] )
	{
		if(e == father || e == bc ) continue ;
		if( sz( (*ptr[e] ) ) == 0 ) 
		{
			deg[ find(x) ]++ ;
			deg[ find(e) ]++ ;
			continue ;
		}

		join(x, e) ;

		for(auto p : (*ptr[e] ) )
		{
			(*ptr[x])[p.first] += p.second ;
			if( (*ptr[x])[p.first]  == qtdState[p.first] )	
				(*ptr[x]).erase( (*ptr[x]).find(p.first) ) ;		
		}

		(*ptr[e]).clear() ;
	}

	(*ptr[x])[ state[x] ]++ ;

	if( (*ptr[x])[ state[x] ] == qtdState[ state[x] ] )
		(*ptr[x]).erase( (*ptr[x]).find( state[x] ) ) ;

	return sub ;

}

int main()
{
	scanf("%d %d", &n, &k ) ;
	for(int i = 0 , u , v ; i < n-1 ; i++ )
	{
		scanf("%d %d", &u, &v ) ;

		adj[u].push_back(v) ;
		adj[v].push_back(u) ;

	}
	for(int i = 1 ; i <= n ; i++ ) 
	{
		scanf("%d", &state[i] ) ;

		dsu[i] = i ;
		qtdState[ state[i] ]++ ;
	}

	dfs(1,-1) ;

	int qtd = 0 ;

	for(int i = 1 ; i <= n ; i++ )
		if( find(i) == i && deg[i] == 1 )  qtd++ ;

	printf("%d\n", (qtd+1)/2 ) ;

}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |  scanf("%d %d", &n, &k ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
mergers.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  106 |   scanf("%d %d", &u, &v ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~
mergers.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  114 |   scanf("%d", &state[i] ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~

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