Submission #332534

#	Time	Username	Problem	Language	Result	Execution time	Memory
332534		Lawliet	Mergers (JOI19_mergers)	C++17	100 / 100	915 ms	84788 KiB

mergers

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 500010;

int n;
int curTime;
int qtdWrong, qtdSpecialEdges;

int v[MAXN];
int freq[MAXN];
int sizeGroup[MAXN];
int degree[MAXN];
int U[MAXN], V[MAXN];
int anc[MAXN], rnk[MAXN];

int sub[MAXN];
int nodeTime[MAXN];
int heavyChild[MAXN];
int tin[MAXN], tout[MAXN];

vector<int> adj[MAXN];

int find(int cur)
{
	if( anc[cur] == cur ) return cur;
	return anc[cur] = find( anc[cur] );
}

void join(int i, int j)
{
	i = find(i); j = find(j);

	if( i == j ) return;

	if( rnk[i] < rnk[j] )
		swap( i , j );

	anc[j] = i;
	if( rnk[i] == rnk[j] ) rnk[i]++;
}

void DFSInit(int cur, int p)
{
	sub[cur] = 1;
	tin[cur] = ++curTime;
	nodeTime[ tin[cur] ] = cur;

	for(int i = 0 ; i < (int)adj[cur].size() ; i++) 
	{
		int viz = adj[cur][i];

		if( viz == p ) continue;

		DFSInit( viz , cur );
		sub[cur] += sub[viz];

		if( sub[ heavyChild[cur] ] < sub[viz] )
			heavyChild[cur] = viz;
	}

	tout[cur] = curTime;
}

void add(int node)
{
	if( freq[ v[node] ] == 0 ) qtdWrong++;
	freq[ v[node] ]++;
	if( freq[ v[node] ] == sizeGroup[ v[node] ] ) qtdWrong--;
}

void DFSSack(int cur, int p, bool keep = false)
{
	if( cur == 0 ) return;

	for(int i = 0 ; i < (int)adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];

		if( viz == p ) continue;
		if( viz == heavyChild[cur] ) continue;

		DFSSack( viz , cur );
	}

	DFSSack( heavyChild[cur] , cur , true );

	add( cur );

	for(int i = 0 ; i < (int)adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];

		if( viz == p ) continue;
		if( viz == heavyChild[cur] ) continue;

		for(int j = tin[viz] ; j <= tout[viz] ; j++)
			add( nodeTime[j] );
	}

	if( qtdWrong != 0 )
	{
		join( cur , p );
		qtdSpecialEdges++;
	}

	if( keep ) return;

	qtdWrong = 0;

	for(int i = tin[cur] ; i <= tout[cur] ; i++)
	{
		int node = nodeTime[i];
		freq[ v[node] ] --;
	}
}

int main()
{
	scanf("%d %*d",&n);

	iota( anc + 1 , anc + n + 1 , 1 );

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

		adj[ U[i] ].push_back( V[i] );
		adj[ V[i] ].push_back( U[i] );
	}

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

	DFSInit( 1 , 1 );
	DFSSack( 1 , 1 );

	if( qtdSpecialEdges == n - 1 )
	{
		printf("0\n");
		return 0;
	}

	for(int i = 1 ; i < n ; i++)
	{
		U[i] = find( U[i] );
		V[i] = find( V[i] );

		if( U[i] != V[i] )
			degree[ U[i] ]++, degree[ V[i] ]++;
	}

	int ans = 0;

	for(int i = 1 ; i <= n ; i++)
		if( degree[i] == 1 ) ans++;

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

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  121 |  scanf("%d %*d",&n);
      |  ~~~~~^~~~~~~~~~~~~
mergers.cpp:127:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |   scanf("%d %d",&U[i],&V[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~
mergers.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  135 |   scanf("%d",&v[i]);
      |   ~~~~~^~~~~~~~~~~~

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