oj.uz

Submission #972575

# Submission time Handle Problem Language Result Execution time Memory
972575 2024-04-30T16:21:10 Z LCJLY Mergers (JOI19_mergers) C++14
0 / 100
 190 ms 73920 KB 
#include <bits/stdc++.h>
using namespace std;
	
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,long long>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

int n,k;
vector<int>adj[500005];
int two[22][500005];
int in[500005];
int out[500005];
int d[500005];
int ptr=0;


void dfs(int index, int par){
	in[index]=++ptr;
	for(int x=0;x<20;x++){
		two[x+1][index]=two[x][two[x][index]];
	}
	
	for(auto it:adj[index]){
		if(it==par) continue;
		d[it]=d[index]+1;
		two[0][it]=index;
		dfs(it,index);
	}
	out[index]=ptr;
}

int lca(int a, int b){
	if(d[a]>d[b]) swap(a,b);
	int diff=d[b]-d[a];
	for(int x=0;x<20;x++){
		if(diff&(1<<x)){
			b=two[x][b];
		}
	}
	if(a==b) return a;
	for(int x=19;x>=0;x--){
		if(two[x][a]!=two[x][b]){
			a=two[x][a];
			b=two[x][b];
		}
	}
	return two[0][a];
}

struct DSU{
	vector<int>e;
	void init(int n){
		e=vector<int>(n,-1);
	}
	
	int get(int x){return e[x]<0?x:e[x]=get(e[x]);}
	
	bool unite(int x, int y){
		x=get(x); y=get(y);
		if(x==y) return 0;
		if(d[x]>d[y]) swap(x,y);
		e[x]+=e[y];
		e[y]=x;
		return 1;
	}
};

bool cmp(int a, int b){
	return in[a]<in[b];
}

DSU dsu;
bool visited[500005];
int deg[500005];

void solve(){
	cin >> n >> k; 
	
	vector<pii>edge;
	int temp,temp2;
	for(int x=0;x<n-1;x++){
		cin >> temp >> temp2;
		adj[temp].push_back(temp2);
		adj[temp2].push_back(temp);
		edge.push_back({temp,temp2});
	}
	
	dfs(1,-1);
	vector<int>v[k+5];
	
	for(int x=1;x<=n;x++){
		cin >> temp;
		v[temp].push_back(x);
	}
	
	dsu.init(n+5);
	
	for(int x=1;x<=k;x++){
		if((int)v[x].size()<=1) continue;
		sort(v[x].begin(),v[x].end(),cmp);
		for(int y=1;y<(int)v[x].size();y++){
			int hold=lca(v[x][y],v[x][y-1]);
			int cur=dsu.get(v[x][y-1]);
			while(d[cur]>d[hold]){
				dsu.unite(cur,two[0][cur]);
				cur=dsu.get(cur);
			}
			cur=dsu.get(v[x][y]);
			while(d[cur]>d[hold]){
				dsu.unite(cur,two[0][cur]);
				cur=dsu.get(cur);
			}
		}
	}
	
	int counter=0;
	for(int x=0;x<n-1;x++){
		int a=edge[x].first;
		int b=edge[x].second;
		a=dsu.get(a);
		b=dsu.get(b);
		if(a==b) continue;
		deg[a]++;
		deg[b]++;
	}
	
	for(int x=1;x<=n;x++){
		int hold=dsu.get(x);
		if(visited[hold]) continue;
		visited[hold]=true;
		if(deg[x]==1) counter++;
	}
	
	cout << (counter+1)/2;
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//freopen("in.txt","r",stdin);
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 52568 KB Output is correct
2 Correct 8 ms 52572 KB Output is correct
3 Correct 8 ms 52568 KB Output is correct
4 Correct 8 ms 52568 KB Output is correct
5 Correct 8 ms 52568 KB Output is correct
6 Correct 9 ms 54616 KB Output is correct
7 Correct 8 ms 54620 KB Output is correct
8 Correct 10 ms 54872 KB Output is correct
9 Correct 8 ms 54620 KB Output is correct
10 Correct 8 ms 54620 KB Output is correct
11 Correct 8 ms 54620 KB Output is correct
12 Incorrect 8 ms 56668 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 52568 KB Output is correct
2 Correct 8 ms 52572 KB Output is correct
3 Correct 8 ms 52568 KB Output is correct
4 Correct 8 ms 52568 KB Output is correct
5 Correct 8 ms 52568 KB Output is correct
6 Correct 9 ms 54616 KB Output is correct
7 Correct 8 ms 54620 KB Output is correct
8 Correct 10 ms 54872 KB Output is correct
9 Correct 8 ms 54620 KB Output is correct
10 Correct 8 ms 54620 KB Output is correct
11 Correct 8 ms 54620 KB Output is correct
12 Incorrect 8 ms 56668 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 52568 KB Output is correct
2 Correct 8 ms 52572 KB Output is correct
3 Correct 8 ms 52568 KB Output is correct
4 Correct 8 ms 52568 KB Output is correct
5 Correct 8 ms 52568 KB Output is correct
6 Correct 9 ms 54616 KB Output is correct
7 Correct 8 ms 54620 KB Output is correct
8 Correct 10 ms 54872 KB Output is correct
9 Correct 8 ms 54620 KB Output is correct
10 Correct 8 ms 54620 KB Output is correct
11 Correct 8 ms 54620 KB Output is correct
12 Incorrect 8 ms 56668 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 67512 KB Output is correct
2 Correct 68 ms 73920 KB Output is correct
3 Incorrect 9 ms 55128 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 52568 KB Output is correct
2 Correct 8 ms 52572 KB Output is correct
3 Correct 8 ms 52568 KB Output is correct
4 Correct 8 ms 52568 KB Output is correct
5 Correct 8 ms 52568 KB Output is correct
6 Correct 9 ms 54616 KB Output is correct
7 Correct 8 ms 54620 KB Output is correct
8 Correct 10 ms 54872 KB Output is correct
9 Correct 8 ms 54620 KB Output is correct
10 Correct 8 ms 54620 KB Output is correct
11 Correct 8 ms 54620 KB Output is correct
12 Incorrect 8 ms 56668 KB Output isn't correct
13 Halted 0 ms 0 KB -