Submission #200387

#	Time	Username	Problem	Language	Result	Execution time	Memory
200387		arnold518	Mergers (JOI19_mergers)	C++14	0 / 100	142 ms	45300 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], A[MAXN+10];
int par[MAXN+10][30], dep[MAXN+10];

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

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

int B[MAXN+10], ppar[MAXN+10], cnt[MAXN+10], ans;

int Find(int x) { return x==ppar[x] ? x : ppar[x]=Find(ppar[x]); }
void Union(int x, int y) { x=Find(x); y=Find(y); ppar[x]=y; }

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

int main()
{
	int i, j;

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

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

	for(i=1; i<=K; i++)
	{
		for(j=1; j<A[i].size(); j++)
		{
			int u=A[i][j-1], v=A[i][j], w=lca(u, v);
			B[u]++; B[v]++; B[w]--; B[w]--;
		}
	}

	dfs2(1, 1);
	for(i=2; i<=N; i++)
	{
		int u=i, v=par[u][0];
		cnt[Find(u)]++; cnt[Find(v)]++;
	}

	for(i=1; i<=N; i++) if(cnt[i]==1) ans++;
	ans++; ans/=2;
	printf("%d", ans);
}

Compilation message (stderr)

mergers.cpp: In function 'int lca(int, int)':
mergers.cpp:26:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
mergers.cpp: In function 'int main()':
mergers.cpp:75:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=1; j<A[i].size(); j++)
            ~^~~~~~~~~~~~
mergers.cpp:54: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:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~

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