oj.uz

Submission #332580

# Submission time Handle Problem Language Result Execution time Memory
332580 2020-12-02T22:14:31 Z CaroLinda Mergers (JOI19_mergers) C++11
0 / 100
 68 ms 32996 KB 
#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] ;
	
	map<int,int> &it = (*ptr[x] );

	if( sz(it) == 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] ) )
		{
			it[p.first] += p.second ;
			if( it[p.first]  == qtdState[p.first] )	
				it.erase( it.find(p.first) ) ;		
		}

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

	it[ state[x] ]++ ;

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


}

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

mergers.cpp: In function 'int dfs(int, int)':
mergers.cpp:100:1: warning: no return statement in function returning non-void [-Wreturn-type]
  100 | }
      | ^
mergers.cpp: In function 'int main()':
mergers.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |  scanf("%d %d", &n, &k ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
mergers.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |   scanf("%d %d", &u, &v ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~
mergers.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |   scanf("%d", &state[i] ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 24300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 24300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 24300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 68 ms 32996 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 24300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -