제출 #128951

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
128951		roseanne_pcy	Mergers (JOI19_mergers)	C++14	100 / 100	1163 ms	91128 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 = 5e5+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];
int mem[maxn];

void gosubtree(int u = 1, int p = 0)
{
	cnt[u] = 1;
	par[u] = p;
	for(int v : adj[u])
	{
		if(v == p) continue;
		chil[u]++;
		gosubtree(v, u);
		cnt[u] += cnt[v];
	}
}

void solve(int u = 1, int p = 0, bool keep = 1)
{
	ii big = {0, -1};
	tar[u] = 0;
	for(int v : adj[u])
	{
		if(v == p) continue;
		big = max(big, {cnt[v], v});
	}
	int best = big.Y;
	for(int v : adj[u])
	{
		if(v == p) continue;
		if(v == best) continue;
		solve(v, u, 0);
	}
	if(best != -1)
	{
		solve(best, u, 1); bst[u] = bst[best]; 
		tar[u] = tar[best];
	}
	else bst[u] = new vector<int>();
	bst[u]->pb(u);
	mem[col[u]]++;
	if(mem[col[u]] == 1) tar[u] += colcnt[col[u]];
	for(int v : adj[u])
	{
		if(v == p || v == best) continue;
		for(int x : *bst[v])
		{
			bst[u]->pb(x);
			mem[col[x]]++;
			if(mem[col[x]] == 1) tar[u] += colcnt[col[x]];
		}
	}
	bad[u] = (tar[u] == cnt[u]);
	// printf("%d is bad %d\n", u, bad[u]);
	if(!keep)
	{
		for(int x : *bst[u]) mem[col[x]]--;
	}
}
 
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]]++;
	}
	gosubtree(); 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);
}

컴파일 시 표준 에러 (stderr) 메시지

mergers.cpp: In function 'int main()':
mergers.cpp:87: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:90: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:95: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: 22 / 22
• Subtask 5: 30 / 30