oj.uz

Submission #105539

# Submission time Handle Problem Language Result Execution time Memory
105539 2019-04-13T10:54:52 Z zscoder Mergers (JOI19_mergers) C++17
0 / 100
 222 ms 26588 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vi adj[555555];
int tot[555555];
int a[555555];
int bad[555555];
int ct;
int act[555555];
int siz[555555];
int par[555555];
void calcsiz(int u, int p=-1)
{
	par[u]=p;
	if(adj[u].size()>1&&adj[u][0]==p) swap(adj[u][1],adj[u][0]);
	siz[u]=1;
	for(auto &v:adj[u])
	{
		if(v==p) continue;
		calcsiz(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[adj[u][0]]) swap(v,adj[u][0]);
	}
}

vector<int> V;

void dfs2(int u, int p=-1)
{
	V.pb(a[u]);
	if(act[a[u]]==-1)
	{
		ct++; act[a[u]]=tot[a[u]];
	}
	act[a[u]]--;
	for(int v:adj[u])
	{
		if(v==p) continue;
		dfs2(v,u);
	}
}

void prep(int u, int p=-1)
{
	for(int i=1;i<adj[u].size();i++)
	{
		int v=adj[u][i];
		if(v==p) continue;
		prep(v,u);
		while(!V.empty()){act[V.back()]=-1; V.pop_back();}
		ct=0;
	}
	if(adj[u][0]!=p) prep(adj[u][0],u);
	for(int i=1;i<adj[u].size();i++)
	{
		int v=adj[u][i];
		if(v==p) continue;
		dfs2(v,u);
	}
	if(act[a[u]]==-1)
	{
		ct++; act[a[u]]=tot[a[u]];
	}
	act[a[u]]--;
	V.pb(a[u]);
	if(act[a[u]]==0) ct--;
	if(ct==0) bad[u]=1;
	//if(bad[u]) cerr<<"BAD "<<u<<'\n';
}

set<int> S;

void prep2(int u, int p)
{
	for(int v:adj[u])
	{
		if(v==p) continue;
		prep2(v,u);
	}
	S.insert(a[u]);
}

int dp[555555][2];
const int INF = int(1e9);

void dfs(int u, int p=-1)
{
	vi pre(2,INF);
	pre[0]=0;
	for(int v:adj[u])
	{
		if(v==p) continue;
		dfs(v,u);
		vi nw(2,INF);
		for(int i=0;i<2;i++)
		{
			for(int j=0;j<2;j++)
			{
				if(j==0&&bad[v]) continue;
				if(j==0) nw[i]=min(nw[i],pre[i]+dp[v][j]);
				else nw[i^1]=min(nw[i^1],pre[i]+dp[v][j]+(i==1?-1:0));
				//cerr<<i<<' '<<j<<' '<<nw[0]<<' '<<nw[1]<<'\n';
			}
		}
		pre=nw;
		//cerr<<u<<' '<<pre[0]<<' '<<pre[1]<<'\n';
	}
	dp[u][0]=min(pre[0],pre[1]); dp[u][1]=min(pre[0]+1,pre[1]);
	if(bad[u]) dp[u][0]=INF;
	//cerr<<"DP : "<<u<<' '<<dp[u][0]<<' '<<dp[u][1]<<'\n';
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); 
	int n,k; cin>>n>>k;
	if(n==1){cout<<0<<'\n'; return 0;}
	memset(act,-1,sizeof(act));
	for(int i=0;i<n-1;i++)
	{
		int u,v; cin>>u>>v; u--; v--;
		adj[u].pb(v); adj[v].pb(u);
	}
	for(int i=0;i<n;i++)
	{
		cin>>a[i]; a[i]--;
		tot[a[i]]++;
	}
	calcsiz(0);
	/*
	prep(0); bad[0]=0;
	*/
	for(int i=1;i<n;i++)
	{
		prep2(i,par[i]);
		int sum=0;
		for(int v:S) sum+=tot[v];
		if(siz[i]==sum) 
		{
			bad[i]=1;
			//cerr<<i<<'\n';
		}
		S.clear();
	}
	dfs(0);
	cout<<dp[0][0]<<'\n';
}

Compilation message

mergers.cpp: In function 'void prep(int, int)':
mergers.cpp:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<adj[u].size();i++)
              ~^~~~~~~~~~~~~~
mergers.cpp:72:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<adj[u].size();i++)
              ~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 15616 KB Output is correct
2 Correct 17 ms 15616 KB Output is correct
3 Correct 15 ms 15616 KB Output is correct
4 Correct 15 ms 15616 KB Output is correct
5 Correct 16 ms 15616 KB Output is correct
6 Correct 17 ms 15616 KB Output is correct
7 Correct 13 ms 13440 KB Output is correct
8 Correct 15 ms 15616 KB Output is correct
9 Correct 16 ms 15616 KB Output is correct
10 Correct 18 ms 15616 KB Output is correct
11 Correct 15 ms 15616 KB Output is correct
12 Incorrect 17 ms 15616 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 15616 KB Output is correct
2 Correct 17 ms 15616 KB Output is correct
3 Correct 15 ms 15616 KB Output is correct
4 Correct 15 ms 15616 KB Output is correct
5 Correct 16 ms 15616 KB Output is correct
6 Correct 17 ms 15616 KB Output is correct
7 Correct 13 ms 13440 KB Output is correct
8 Correct 15 ms 15616 KB Output is correct
9 Correct 16 ms 15616 KB Output is correct
10 Correct 18 ms 15616 KB Output is correct
11 Correct 15 ms 15616 KB Output is correct
12 Incorrect 17 ms 15616 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 15616 KB Output is correct
2 Correct 17 ms 15616 KB Output is correct
3 Correct 15 ms 15616 KB Output is correct
4 Correct 15 ms 15616 KB Output is correct
5 Correct 16 ms 15616 KB Output is correct
6 Correct 17 ms 15616 KB Output is correct
7 Correct 13 ms 13440 KB Output is correct
8 Correct 15 ms 15616 KB Output is correct
9 Correct 16 ms 15616 KB Output is correct
10 Correct 18 ms 15616 KB Output is correct
11 Correct 15 ms 15616 KB Output is correct
12 Incorrect 17 ms 15616 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 21140 KB Output is correct
2 Correct 222 ms 26588 KB Output is correct
3 Incorrect 30 ms 15872 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 15616 KB Output is correct
2 Correct 17 ms 15616 KB Output is correct
3 Correct 15 ms 15616 KB Output is correct
4 Correct 15 ms 15616 KB Output is correct
5 Correct 16 ms 15616 KB Output is correct
6 Correct 17 ms 15616 KB Output is correct
7 Correct 13 ms 13440 KB Output is correct
8 Correct 15 ms 15616 KB Output is correct
9 Correct 16 ms 15616 KB Output is correct
10 Correct 18 ms 15616 KB Output is correct
11 Correct 15 ms 15616 KB Output is correct
12 Incorrect 17 ms 15616 KB Output isn't correct
13 Halted 0 ms 0 KB -