oj.uz

Submission #894767

# Submission time Handle Problem Language Result Execution time Memory
894767 2023-12-28T23:27:01 Z amirhoseinfar1385 Mergers (JOI19_mergers) C++17
0 / 100
 57 ms 51396 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10;
vector<int>adj[maxn];
map<int,int>mp[maxn];
int cntc[maxn],sz[maxn],n,k,val[maxn],cnt[maxn],res;

bool cmp(int a,int b){
	return sz[a]>sz[b];
}

void pre(int u=1,int par=0){
	if(u!=1){
		sort(adj[u].begin(),adj[u].end());
		adj[u].erase(lower_bound(adj[u].begin(),adj[u].end(),par));
	}
	sz[u]=1;
	for(auto x:adj[u]){
		pre(x,u);
		sz[u]+=sz[x];
	}
	sort(adj[u].begin(),adj[u].end(),cmp);
}
void solve(int u){
	if((int)adj[u].size()==0){
		if(cntc[val[u]]!=1){
			mp[u][val[u]]=1;
		}
		else{
			res++;
			cnt[u]=1;
		}
		return ;
	}
	solve(adj[u][0]);
	cnt[u]=cnt[adj[u][0]];
	swap(mp[adj[u][0]],mp[u]);
	for(int i=1;i<(int)adj[u].size();i++){
		solve(adj[u][i]);
		cnt[u]+=cnt[adj[u][i]];
		for(auto x:mp[adj[u][i]]){
			mp[u][x.first]+=x.second;
			if(cntc[x.first]==mp[u][x.first]){
				mp[u].erase(x.first);
			}
		}
	}
	mp[u][val[u]]++;
	if(cntc[val[u]]==mp[u][val[u]]){
		mp[u].erase(val[u]);
	}
	if((int)mp[u].size()==0){
		if(cnt[u]==0){
			res++;
		}
		if(u!=1){
			cnt[u]=1;
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		cin>>val[i];
		cntc[val[i]]++;
	}
	pre(1);
	solve(1);
	if(cnt[1]==1){
		res++;
	}
	if(n==1){
		cout<<0<<"\n";
		return 0;
	}
	cout<<((res+1)/2)<<"\n";
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 43100 KB Output is correct
2 Correct 8 ms 43348 KB Output is correct
3 Correct 8 ms 43352 KB Output is correct
4 Correct 9 ms 43276 KB Output is correct
5 Incorrect 8 ms 43100 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 43100 KB Output is correct
2 Correct 8 ms 43348 KB Output is correct
3 Correct 8 ms 43352 KB Output is correct
4 Correct 9 ms 43276 KB Output is correct
5 Incorrect 8 ms 43100 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 43100 KB Output is correct
2 Correct 8 ms 43348 KB Output is correct
3 Correct 8 ms 43352 KB Output is correct
4 Correct 9 ms 43276 KB Output is correct
5 Incorrect 8 ms 43100 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 51396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 43100 KB Output is correct
2 Correct 8 ms 43348 KB Output is correct
3 Correct 8 ms 43352 KB Output is correct
4 Correct 9 ms 43276 KB Output is correct
5 Incorrect 8 ms 43100 KB Output isn't correct
6 Halted 0 ms 0 KB -