oj.uz

Submission #333167

# Submission time Handle Problem Language Result Execution time Memory
333167 2020-12-04T21:16:22 Z Kenzo_1114 Mergers (JOI19_mergers) C++17
0 / 100
 151 ms 51676 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 500010;

int n, k, qtt[MAXN], g[MAXN], in[MAXN], ans[MAXN];

int par[MAXN], depth[MAXN], need[MAXN], have[MAXN];
set<int> s[MAXN];
set<int> :: iterator it;

vector<int> graph[MAXN];
bool marc[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),	ans[v] += ans[u];
	}
}

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;
	have[b] += have[a];

	for(it = s[a].begin(); it != s[a].end(); it++)
		if(s[b].find(*it) == s[b].end()) need[b] += qtt[*it], s[b].insert(*it);	
	
	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[u]++, in[v]++;
	}

	queue<int> q;
	for(int i = 1; i <= n; i++)	
	{
		scanf("%d", &g[i]);	qtt[g[i]]++;
		if(in[i] == 1) q.push(i);
	}

	for(int i = 1; i <= n; i++)
	{
		par[i] = i;
		need[i] = qtt[g[i]];
		have[i] = 1;
		s[i].insert(g[i]);
	}

	int root = 0;
	while(!q.empty())
	{
		int v = q.front(); q.pop();
		marc[v] = true;

		for(int i = 0; i < (int) graph[v].size(); i++)
		{
			int u = graph[v][i];
			if(marc[u])	continue;

			in[u]--;
			if(have[find(v)] == need[find(v)])	ans[v]++, root = v;
			join(v, u);
			if(in[u] <= 1)	q.push(u), marc[i] = true;
		}
	}

//	for(int i = 1; i <= n; i++)	printf("ans[%d] = %d\n", i, ans[i]);

	dfs(root, root);

//	for(int i = 1; i <= n; i++)	printf("ans[%d] = %d\n", i, ans[i]);	

	printf("%d\n", (ans[root] + 1) >> 1);
}

/*

5 4
1 2
2 3
3 4
3 5
1
2
1
3
4

*/

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35564 KB Output is correct
2 Correct 24 ms 35564 KB Output is correct
3 Correct 24 ms 35564 KB Output is correct
4 Correct 24 ms 35564 KB Output is correct
5 Correct 24 ms 35564 KB Output is correct
6 Correct 24 ms 35564 KB Output is correct
7 Correct 24 ms 35564 KB Output is correct
8 Correct 24 ms 35564 KB Output is correct
9 Correct 24 ms 35564 KB Output is correct
10 Correct 24 ms 35564 KB Output is correct
11 Correct 24 ms 35564 KB Output is correct
12 Incorrect 24 ms 35564 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35564 KB Output is correct
2 Correct 24 ms 35564 KB Output is correct
3 Correct 24 ms 35564 KB Output is correct
4 Correct 24 ms 35564 KB Output is correct
5 Correct 24 ms 35564 KB Output is correct
6 Correct 24 ms 35564 KB Output is correct
7 Correct 24 ms 35564 KB Output is correct
8 Correct 24 ms 35564 KB Output is correct
9 Correct 24 ms 35564 KB Output is correct
10 Correct 24 ms 35564 KB Output is correct
11 Correct 24 ms 35564 KB Output is correct
12 Incorrect 24 ms 35564 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35564 KB Output is correct
2 Correct 24 ms 35564 KB Output is correct
3 Correct 24 ms 35564 KB Output is correct
4 Correct 24 ms 35564 KB Output is correct
5 Correct 24 ms 35564 KB Output is correct
6 Correct 24 ms 35564 KB Output is correct
7 Correct 24 ms 35564 KB Output is correct
8 Correct 24 ms 35564 KB Output is correct
9 Correct 24 ms 35564 KB Output is correct
10 Correct 24 ms 35564 KB Output is correct
11 Correct 24 ms 35564 KB Output is correct
12 Incorrect 24 ms 35564 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 46692 KB Output is correct
2 Correct 151 ms 51676 KB Output is correct
3 Incorrect 28 ms 36332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35564 KB Output is correct
2 Correct 24 ms 35564 KB Output is correct
3 Correct 24 ms 35564 KB Output is correct
4 Correct 24 ms 35564 KB Output is correct
5 Correct 24 ms 35564 KB Output is correct
6 Correct 24 ms 35564 KB Output is correct
7 Correct 24 ms 35564 KB Output is correct
8 Correct 24 ms 35564 KB Output is correct
9 Correct 24 ms 35564 KB Output is correct
10 Correct 24 ms 35564 KB Output is correct
11 Correct 24 ms 35564 KB Output is correct
12 Incorrect 24 ms 35564 KB Output isn't correct
13 Halted 0 ms 0 KB -