Submission #232120

#	Time	Username	Problem	Language	Result	Execution time	Memory
232120		oolimry	Mergers (JOI19_mergers)	C++14	100 / 100	870 ms	80972 KiB

mergers

#include <bits/stdc++.h>
using namespace std;

int n, k; 
vector<int> adj[500005];
int sz[500005];
int heavy[500005];
int depth[500005];
int head[500005];
int p[500005];
int pos[500005];

void dfs(int u){
	sz[u] = 1;
	int maxChild = 0;
	for(int v : adj[u]){
		if(sz[v] != 0) continue;
		depth[v] = depth[u] + 1;
		dfs(v);
		sz[u] += sz[v];
		p[v] = u;
		if(sz[v] > maxChild){
			heavy[u] = v;
			maxChild = sz[v];
		}
	}
}

int cnt = 0;
void decompose(int u, int h){
	head[u] = h;
	pos[u] = cnt; cnt++;
	if(heavy[u] != 0) decompose(heavy[u], h);
	for(int v : adj[u]){
		if(sz[v] < sz[u] && v != heavy[u]){
			decompose(v,v);
		}
	}
}

int preState[500005];

int prefix[500005];

void update(int l, int r){
	prefix[l]++;
	prefix[r+1]--;
}

struct UFDS{
	int p[500005];
	void init() { for(int i = 0;i <= n;i++) p[i] = i; }
	
	int findSet(int u){
		if(p[u] == u) return u;
		else return p[u] = findSet(p[u]);
	}
	
	void unionSet(int u, int v){
		u = findSet(u); v = findSet(v);
		if(u == v) return;
		
		if((u^v)&1) swap(u,v);
		p[u] = v;
	}
} uf;

int compressAdj[500005];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> k;
	for(int i = 0;i < n-1;i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	int root = -1;
	for(int i = 1;i <= n;i++){
		if(adj[i].size() != 1){
			root = i;
			break;
		}
	}
	
	if(root == -1){ ///n==2 or n==1
		cout << k-1; return 0;
	}
	
	dfs(root);
	decompose(root, root);
	
	//for(int i = 1;i <= n;i++) cout << pos[i] << " " << head[i] << "\n";
	
	for(int i = 1;i <= n;i++){
		int state; cin >> state;
		if(preState[state] != 0){
			int a = i, b = preState[state];
			if(depth[a] > depth[b]) swap(a,b);
			for(;head[a] != head[b];b = p[head[b]]){
				if(depth[head[a]] > depth[head[b]]) swap(a,b);
				update(pos[head[b]], pos[b]);
			}
			if(depth[a] > depth[b]) swap(a,b);
			update(pos[a]+1,pos[b]);
		}
		preState[state] = i;
	}
	
	for(int i = 1;i <= n;i++) prefix[i] += prefix[i-1];
	
	uf.init();
	
	for(int i = 1;i <= n;i++){
		if(i == root) continue;
		if(prefix[pos[i]] == 0) continue;
		
		uf.unionSet(i, p[i]);
	}
	
	for(int i = 1;i <= n;i++){
		if(i == root) continue;
		if(prefix[pos[i]] != 0) continue;
		
		compressAdj[uf.findSet(i)]++;
		compressAdj[uf.findSet(p[i])]++;
	}
	
	int leaves = 0;
	for(int i = 1;i <= n;i++){
		if(compressAdj[i] == 1) leaves++;
	}
	
	cout << (leaves+1)/2;
}

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30