Submission #128906

#	Time	Username	Problem	Language	Result	Execution time	Memory
128906		roseanne_pcy	Mergers (JOI19_mergers)	C++14	48 / 100	3037 ms	25760 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 merge(vector<int> &A, vector<int> &B)
{
	vector<int> res;
	int n = A.size(), m = B.size();
	int i = 0, j = 0;
	while(i< n && j< m)
	{
		if(A[i]< B[j])
		{
			if(res.empty() || res.back() != A[i]) res.pb(A[i]);
			i++;
		}
		else
		{
			if(res.empty() || res.back() != B[j]) res.pb(B[j]);
			j++;
		}
	}
	while(i< n)
	{
		if(res.empty() || res.back() != A[i]) res.pb(A[i]);
		i++;
	}
	while(j< m)
	{
		if(res.empty() || res.back() != B[j]) res.pb(B[j]);
		j++;
	}
	A = res;
}
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;
			merge(bst[u], bst[v]);
		}
	}
	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]);
		}
	}
	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);
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:89: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:92: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:97: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