Submission #128921

#	Time	Username	Problem	Language	Result	Execution time	Memory
128921		roseanne_pcy	Mergers (JOI19_mergers)	C++14	48 / 100	3054 ms	25788 KiB

mergers

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
 
const int maxn = 1e5+5;
 
int n, k;
 
vector<int> adj[maxn];
int col[maxn];
int colcnt[maxn];
int tar[maxn];
vector<int> bst[maxn];
int cnt[maxn];
bool bad[maxn];
bool notbad[maxn];
int par[maxn];
bool vis[maxn];
int om[maxn];
int chil[maxn];
 
void solve(int u = 1, int p = 0)
{
	cnt[u] = 1;
	ii big = {0, -1};
	bst[u].push_back(col[u]);
	tar[u] = 0;
	par[u] = p;
	for(int v : adj[u])
	{
		if(v == p) continue;
		solve(v, u);
		chil[u]++;
		big = max(big, {bst[v].size(), v});
		cnt[u] += cnt[v];
	}
	if(big.Y != -1)
	{
		int best = big.Y;
		swap(bst[u], bst[best]);
		for(int v : adj[u])
		{
			if(v == p) continue;
			for(int x : bst[v]) bst[u].push_back(x);
		}
		sort(bst[u].begin(), bst[u].end());
		bst[u].resize(unique(bst[u].begin(), bst[u].end())-bst[u].begin());
	}
	for(int x : bst[u]) tar[u] += colcnt[x];
	bad[u] = (tar[u] == cnt[u]);
}
 
int main()
{
	scanf("%d %d", &n, &k);
	for(int i = 0; i< n-1; i++)
	{
		int u, v; scanf("%d %d", &u, &v);
		adj[u].pb(v); adj[v].pb(u);
	}
	for(int i = 1; i<= n; i++)
	{
		scanf("%d", &col[i]);
		colcnt[col[i]]++;
	}
	solve();
	queue<int> q;
	for(int i = 2; i<= n; i++)
	{
		if(bad[i])
		{
			q.push(par[i]);
			// printf("%d is bad\n", i);
		}
	}
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		notbad[u] = true;
		int v = par[u];
		if(!v) continue;
		if(!vis[v])
		{
			vis[v] = true;
			q.push(v);
		}
	}
	int res = 0;
	for(int i = 2; i<= n; i++)
	{
		if(bad[i] && !notbad[i])
		{
			res++;
			om[par[i]]++;
		}
	}
	for(int i = 1; i<= n; i++)
	{
		if(!chil[i]) q.push(i);
	}
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		int v = par[u];
		if(!v) continue;
		om[v] += om[u];
		chil[v]--;
		if(chil[v] == 0) q.push(v);
	}
	bool superbad = false;
	for(int i = 2; i<= n; i++)
	{
		if(bad[i] && om[i] == res)
		{
			superbad = true;
			printf("%d\n", (res+superbad+1)/2);
			return 0;
		}
	}
	printf("%d\n", (res+superbad+1)/2);
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:61: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:64:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d %d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &col[i]);
   ~~~~~^~~~~~~~~~~~~~~

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