Submission #126003

#	Time	Username	Problem	Language	Result	Execution time	Memory
126003		TadijaSebez	Mergers (JOI19_mergers)	C++11	100 / 100	2306 ms	128972 KiB

mergers

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=500050;
const int L=19;
vector<int> my[N],E[N];
int s[N],par[N][L],dep[N],sum[N];
void DFS(int u, int p)
{
	par[u][0]=p;
	dep[u]=dep[p]+1;
	for(int i=1;i<L;i++) par[u][i]=par[par[u][i-1]][i-1];
	for(int v:E[u]) if(v!=p) DFS(v,u);
}
int LCA(int u, int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=L-1;~i;i--) if(dep[par[u][i]]>=dep[v]) u=par[u][i];
	for(int i=L-1;~i;i--) if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
	return u==v?v:par[v][0];
}
void Solve(int u, int p)
{
	for(int v:E[u]) if(v!=p) Solve(v,u),sum[u]+=sum[v];
}
int csz,deg[N];
void Compress(int u, int p, int c)
{
	for(int v:E[u]) if(v!=p)
	{
		if(sum[v]==0)
		{
			csz++;
			deg[c]++;
			deg[csz]++;
			Compress(v,u,csz);
		}
		else Compress(v,u,c);
	}
}
int main()
{
    int n,k,u,v;
	scanf("%i %i",&n,&k);
	for(int i=1;i<n;i++) scanf("%i %i",&u,&v),E[u].pb(v),E[v].pb(u);
	for(int i=1;i<=n;i++) scanf("%i",&s[i]),my[s[i]].pb(i);
	DFS(1,0);
	for(int i=1;i<=k;i++)
	{
		for(int j=1;j<my[i].size();j++)
		{
			int lca=LCA(my[i][j-1],my[i][j]);
			sum[my[i][j-1]]++;
			sum[my[i][j]]++;
			sum[lca]-=2;
		}
	}
	Solve(1,0);
	csz=1;
	Compress(1,0,1);
	int cnt=0;
	for(int i=1;i<=csz;i++) if(deg[i]==1) cnt++;
	int ans=cnt+1>>1;
	printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1;j<my[i].size();j++)
               ~^~~~~~~~~~~~~
mergers.cpp:63:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int ans=cnt+1>>1;
          ~~~^~
mergers.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~
mergers.cpp:45:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<n;i++) scanf("%i %i",&u,&v),E[u].pb(v),E[v].pb(u);
                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
mergers.cpp:46:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i",&s[i]),my[s[i]].pb(i);
                        ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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