oj.uz

Submission #128950

# Submission time Handle Problem Language Result Execution time Memory
128950 2019-07-11T11:09:06 Z roseanne_pcy Mergers (JOI19_mergers) C++14
0 / 100
 134 ms 27760 KB 
#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(cnt[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(cnt[col[x]] == 1) tar[u] += colcnt[col[x]];
		}
	}
	bad[u] = (tar[u] == cnt[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);
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12152 KB Output is correct
2 Incorrect 12 ms 12152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12152 KB Output is correct
2 Incorrect 12 ms 12152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12152 KB Output is correct
2 Incorrect 12 ms 12152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 26644 KB Output is correct
2 Incorrect 134 ms 27760 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12152 KB Output is correct
2 Incorrect 12 ms 12152 KB Output isn't correct
3 Halted 0 ms 0 KB -