Submission #333178

#	Time	Username	Problem	Language	Result	Execution time	Memory
333178		Kenzo_1114	Mergers (JOI19_mergers)	C++17	0 / 100	164 ms	47408 KiB

mergers

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 500010;
 
int n, k, qtt[MAXN], g[MAXN], in[2][MAXN];
 
int par[MAXN], depth[MAXN], need[MAXN];
set<int> s[MAXN];
set<int> :: iterator it;
int marc[MAXN], specialEdge[MAXN];
vector<int> graph[MAXN];
 
void dfs(int v, int p)
{
	for(int i = 0; i < (int) graph[v].size(); i++)
	{
		int u = graph[v][i];
		if(u != p)	dfs(u, v);
	}
}
 
int find(int v)
{
	return (v == par[v]) ? v : par[v] = find(par[v]);
}
 
void join(int a, int b)
{
	a = find(a), b = find(b);
	if(a == b)	return;
	if(depth[a] > depth[b])	swap(a, b);
 
	par[a] = b;
	need[b] += need[a];
 
	for(it = s[a].begin(); it != s[a].end(); it++)
	{
		if(s[b].find(*it) != s[b].end()) need[b] -= qtt[*it];
		else s[b].insert(*it);
	}
	s[a].clear();
 
	if(depth[a] == depth[b])	depth[b]++;
}
 
int main ()
{
	scanf("%d %d", &n, &k);
 
	for(int i = 0, u, v; i < n - 1; i++)
	{
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
		graph[v].push_back(u);
		in[0][u]++, in[0][v]++;
	}
 
	stack <int, vector <int> > q;
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &g[i]);	qtt[g[i]]++;
		in[1][i] = in[0][i];
		if(in[0][i] == 1)	q.push(i);
	}
 
	for(int i = 1; i <= n; i++)
	{
		par[i] = i;
		need[i] = qtt[g[i]] - 1;
		s[i].insert(g[i]);
	}
 
	while(!q.empty())
	{
		int v = q.top(); q.pop();
        marc[v] = 1;
		for(int i = 0; i < (int) graph[v].size(); i++)
		{
			int u = graph[v][i];
            if(marc[u] == 1) continue;
            in[0][u]--;
			if(need[find(v)] == 0)	specialEdge[v] = true;
			join(v, u);
			if(in[0][u] <= 1)	q.push(u);
		}
	}
 
	for(int i = 1; i <= n; i++)
		if(in[1][i] == 1)	q.push(i);
 
	int ans = 0;
	while(!q.empty())
	{
		int v = q.top(); q.pop();
 
		for(int i = 0; i < (int) graph[v].size(); i++)
		{
			int u = graph[v][i];
			in[1][u]--;
 
			if(specialEdge[v]){	ans++; in[1][u] = 0; continue;	}
			if(in[1][u] == 1)	in[1][u] = 0, q.push(u);
		}
	}
 
	printf("%d\n", (ans + 1) >> 1);
}
 
/*
 
5 4
1 2
2 3
3 4
3 5
1
2
1
3
4
 
*/

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |  scanf("%d %d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   scanf("%d", &g[i]); qtt[g[i]]++;
      |   ~~~~~^~~~~~~~~~~~~

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