Submission #802966

#	Time	Username	Problem	Language	Result	Execution time	Memory
802966		aymanrs	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	345 ms	69648 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int L = 18;
struct node {
	vector<node*> l; // neighbors in the original graph
	vector<node*> c; // children in the CT
	int a, id; // a is the value of the node, id is its index
	bool v = false; // initially, no node is marked
	node* anc[L];
};
// <DSU>
int f(int i, int r[]){ // find representant of i
	if(r[i] == i) return i;
	return r[i] = f(r[i], r);
}
void merge(int a, int b, int r[], int s[]){
	a = f(a, r);
	b = f(b, r);
	if(a == b) return;
	if(s[a] > s[b]){
		r[b] = a;
		s[a] += s[b];
	} else {
		r[a] = b;
		s[b] += s[a];
	}
}
// </DSU>
int dist(node* u, node* v){
	if(u->a < v->a) swap(u, v);
	int d = u->a-v->a;
	for(int i = 0;i < L;i++) if(d&(1<<i)) u = u->anc[i];
	if(u == v) return d;
	for(int i = L-1;i >= 0;i--){
		if(u->anc[i] != v->anc[i]){
			u = u->anc[i];
			v = v->anc[i];
			d += 2<<i;
		}
	}
	return d+2;
}
long long dfs(node* n){
	long long r = 0;
	for(node* c : n->c) r = max(r, dfs(c)+dist(n, c));
	return r;
}
void se(node* n, node* p, int d){
	n->anc[0] = p;
	n->a = d;
	for(int i = 1;i < L;i++) n->anc[i] = n->anc[i-1]->anc[i-1]; 
	for(node* c : n->l) if(c!=p) se(c, n, d+1);
}
void solve(){
	// <boring setup>
	int n,u,v;
	cin >> n;
	int m = n-1;
	node g[n+1];
	int o[n], r[n+1], s[n+1];
	node* c[n+1]; // c[u] is the node with maximum value that u is connected to in the DSU, if u is its own representant
	for(int i = 1;i <= n;i++) {
		cin >> g[i].a;
		g[i].id = i;
		r[i] = i;
		s[i] = 1;
		c[i] = &g[i];
		o[i-1] = i;
	}
	while(m--){
		cin >> u >> v;
		g[u].l.push_back(&g[v]);
		g[v].l.push_back(&g[u]);
	}
	// </boring setup>
	sort(o, o+n, [&g](int a, int b){return g[a].a < g[b].a;}); // sorting the nodes by value
	for(int j = 0;j < n;j++){
		node* d = &g[o[j]]; // d is the current node
		d->v = true; // mark the current node
		for(node* x : d->l){ // iterate over the neighbors of d
			if(!x->v || f(x->id, r) == f(d->id, r)) continue; // x is unmarked or it's already connected to d
			d->c.push_back(c[f(x->id, r)]); // add and edge in the CT between d and the node with maximum value that is connected to x
			merge(x->id, d->id, r, s); // connect d and x in the DSU
			c[f(d->id, r)] = d;
		}
	}
	// Use the CT
	se(&g[1], &g[1], 0);
	cout << dfs(&g[o[n-1]]) << '\n';
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26