Submission #128273

#	Time	Username	Problem	Language	Result	Execution time	Memory
128273		mohammedehab2002	Mergers (JOI19_mergers)	C++11	100 / 100	1603 ms	144248 KiB

mergers

#include <iostream>
#include <vector>
#include <set>
using namespace std;
int st[500005],dep[500005],dp[20][500005],q[500005],par[500005],deg[500005];
set<pair<int,int> > s;
vector<int> v[500005],inv[500005],comp[500005];
void pre(int node,int p)
{
	dep[node]=dep[p]+1;
	dp[0][node]=p;
	for (int i=1;i<20;i++)
	dp[i][node]=dp[i-1][dp[i-1][node]];
	for (int u:v[node])
	{
		if (u!=p)
		pre(u,node);
	}
}
int lca(int u,int v)
{
	if (dep[u]<dep[v])
	swap(u,v);
	int dist=dep[u]-dep[v];
	for (int i=0;i<20;i++)
	{
		if (dist&(1<<i))
		u=dp[i][u];
	}
	if (u==v)
	return u;
	for (int i=19;i>=0;i--)
	{
		if (dp[i][u]!=dp[i][v])
		{
			u=dp[i][u];
			v=dp[i][v];
		}
	}
	return dp[0][u];
}
int find(int x)
{
	if (par[x]!=x)
	par[x]=find(par[x]);
	return par[x];
}
void Union(int x,int y)
{
	x=find(x);
	y=find(y);
	if (x!=y)
	par[x]=y;
}
void update(int u,int v)
{
	while (dep[u]>dep[v])
	{
		Union(u,dp[0][u]);
		u=find(u);
	}
}
void get(int node,int p,int to)
{
	for (int u:v[node])
	{
		if (u!=p)
		{
			if (find(u)==find(node))
			get(u,node,to);
			else
			{
				deg[to]++;
				deg[u]++;
				get(u,node,u);
			}
		}
	}
}
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for (int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for (int i=1;i<=n;i++)
	{
		par[i]=i;
		scanf("%d",&st[i]);
		inv[st[i]].push_back(i);
	}
	pre(1,0);
	for (int i=1;i<=k;i++)
	{
		int node=inv[i][0];
		for (int u:inv[i])
		node=lca(node,u);
		for (int u:inv[i])
		q[u]=node;
	}
	for (int i=1;i<=n;i++)
	update(i,q[i]);
	get(1,0,1);
	int cnt=0;
	for (int i=1;i<=n;i++)
	cnt+=(deg[i]==1);
	printf("%d",(cnt+1)/2);
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:83: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:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~
mergers.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&st[i]);
   ~~~~~^~~~~~~~~~~~~

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