Submission #295220

#	Time	Username	Problem	Language	Result	Execution time	Memory
295220		arnold518	Mergers (JOI19_mergers)	C++14	100 / 100	1645 ms	156408 KiB

mergers

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e5;

int N, K;
vector<int> adj[MAXN+10];
vector<int> V[MAXN+10];

int L[MAXN+10], R[MAXN+10], cnt, dep[MAXN+10];
int par[MAXN+10][30], A[MAXN+10];
int dp[MAXN+10], P[MAXN+10], deg[MAXN+10];

void dfs(int now, int bef, int d)
{
	L[now]=++cnt;
	par[now][0]=bef;
	dep[now]=d;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs(nxt, now, d+1);
	}
	R[now]=cnt;
}

int lca(int u, int v)
{
	if(dep[u]>dep[v]) swap(u, v);
	for(int i=20; i>=0; i--) if(dep[par[v][i]]>=dep[u]) v=par[v][i];
	if(u==v) return u;
	for(int i=20; i>=0; i--) if(par[u][i]!=par[v][i]) u=par[u][i], v=par[v][i];
	return par[u][0];
}

void dfs2(int now, int bef)
{
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs2(nxt, now);
		dp[now]+=dp[nxt];
	}
}

void dfs3(int now, int bef)
{
	if(dp[now]==0)
	{
		P[now]=now;
		if(now!=bef) deg[now]++, deg[P[bef]]++;
	}
	else P[now]=P[bef];
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs3(nxt, now);
	}
}

int main()
{
	scanf("%d%d", &N, &K);
	for(int i=1; i<N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i=1; i<=N; i++) scanf("%d", &A[i]), V[A[i]].push_back(i);

	dfs(1, 1, 1);
	for(int i=1; i<=20; i++) for(int j=1; j<=N; j++) par[j][i]=par[par[j][i-1]][i-1];

	for(int i=1; i<=N; i++) dp[i]++;
	for(int i=1; i<=K; i++)
	{
		int w=V[i][0];
		for(auto it : V[i]) w=lca(w, it);
		dp[w]-=V[i].size();
	}

	dfs2(1, 1);
	dfs3(1, 1);

	int ans=0;
	for(int i=1; i<=N; i++) if(deg[i]==1) ans++;
	printf("%d\n", (ans+1)/2);
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |  scanf("%d%d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:75:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |  for(int i=1; i<=N; i++) scanf("%d", &A[i]), V[A[i]].push_back(i);
      |                          ~~~~~^~~~~~~~~~~~~

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