oj.uz

Submission #1114254

# Submission time Handle Problem Language Result Execution time Memory
1114254 2024-11-18T12:56:50 Z Dan4Life Mergers (JOI19_mergers) C++17
0 / 100
 62 ms 45660 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ar2 = array<int,2>;
const int N = (int)5e5+10;
int n, k;
vector<int> adj[N];
int p[N], sz[N];
int a[N], tot[N], deg[N];
map<int,int> S[N];
 
int findSet(int i){return i==p[i]?i:p[i]=findSet(p[i]);}
void unionSet(int i, int j){
	int x = findSet(i), y = findSet(j);
	if(x==y) return;
	if(sz[x]<sz[y])swap(x,y);
	p[y] = x, sz[x]+=sz[y];
}
 
void dfs(int s, int p){
	S[s][a[s]]=1;
	if(S[s][a[s]]==tot[a[s]]) 
		S[s].erase(S[s].find(a[s]));
	for(auto u : adj[s]){
		if(u==p) continue;
		dfs(u,s);
		if(sz(S[s]) < sz(S[u])) S[s].swap(S[u]);
		for(auto [v,w] : S[u]){
			S[s][v]+=w;
			if(S[s][v]==tot[v])
				S[s].erase(S[s].find(v));
		}
	}
	if(p and !!sz(S[s])) deg[s]++,deg[p]++;
}
 
int32_t main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k;
	for(int i = 1; i <= n; i++) p[i]=i,sz[i]=1;
	for(int i = 1; i < n; i++){
		int a, b; cin >> a >> b;
		adj[a].pb(b); adj[b].pb(a);
	}
	for(int i = 1; i <= n; i++)
		cin >> a[i], tot[a[i]]++;
	dfs(1,0);
	for(int i = 1; i <= n; i++)
		for(int j : adj[i])
			if(findSet(i)!=findSet(j)) 
				deg[findSet(i)]++;
	int cnt = 1;
	for(int i = 1; i <= n; i++) cnt+=(deg[i]==1);
	cout << cnt/2 << "\n";
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 45660 KB Output is correct
2 Correct 60 ms 41408 KB Output is correct
3 Incorrect 16 ms 36176 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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