oj.uz

Submission #949431

# Submission time Handle Problem Language Result Execution time Memory
949431 2024-03-19T08:45:38 Z pcc Mergers (JOI19_mergers) C++17
0 / 100
 91 ms 64624 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int B = 20;
const int mxn = 5e5+10;
vector<int> tree[mxn],tree2[mxn];
int N,K;
int arr[mxn];
vector<int> col[mxn];
int par[mxn][B],dep[mxn];
bitset<mxn> done;
int deg[mxn];

struct DSU{
	int dsu[mxn],sz[mxn],high[mxn];
	DSU(){
		for(int i = 1;i<mxn;i++){
			dsu[i] = i;
			sz[i] = 1;
			high[i] = i;
		}
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		a = root(a),b = root(b);
		if(a == b)return;
		if(sz[a]<sz[b])swap(a,b);
		dsu[b] = a;
		sz[a] += sz[b];
		if(dep[high[b]]<dep[high[a]])high[a] = high[b];
		return;
	}
};
DSU dsu;

void dfs(int now){
	for(int i = 1;i<B;i++){
		par[now][i] = par[par[now][i-1]][i-1];
	}
	for(auto nxt:tree[now]){
		if(nxt == par[now][0])continue;
		par[nxt][0] = now;
		dep[nxt] = dep[now]+1;
		dfs(nxt);
	}
	return;
}
int LCA(int a,int b){
	if(dep[a]<dep[b])swap(a,b);
	int d = dep[a]-dep[b];
	for(int i = B-1;i>=0;i--){
		if(d&(1<<i))a = par[a][i];
	}
	for(int i = B-1;i>=0;i--){
		if(par[a][i] != par[b][i])a = par[a][i],b = par[b][i];
	}
	return a == b?a:par[a][0];
}

void shrink(int c){
	int p = col[c][0];
	for(auto &i:col[c])p = LCA(i,p);
	for(auto now:col[c]){
		while(dep[now]>dep[p]){
			dsu.onion(now,par[now][0]);
			now = dsu.high[dsu.root(now)];
		}
	}
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>K;
	for(int i = 1;i<N;i++){
		int a,b;
		cin>>a>>b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	for(int i = 1;i<=N;i++){
		cin>>arr[i];
		col[arr[i]].push_back(i);
	}
	par[1][0] = 1;
	dfs(1);
	for(int i = 1;i<=K;i++){
		if(!done[i])shrink(i);
	}
	int cnt = 0;
	int one = 0;
	for(int i = 1;i<=N;i++){
		cnt += (dsu.root(i) == i);
		for(auto nxt:tree[i]){
			if(dsu.root(i) == dsu.root(nxt))continue;
			deg[dsu.root(nxt)]++;
		}
	}
	for(int i = 1;i<=N;i++)one += (deg[i] == 1);
	cout<<(cnt==1?0:one-1);
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 61644 KB Output is correct
2 Incorrect 91 ms 64624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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