oj.uz

Submission #857732

# Submission time Handle Problem Language Result Execution time Memory
857732 2023-10-06T18:09:11 Z Hakiers Cat Exercise (JOI23_ho_t4) C++17
0 / 100
 159 ms 36140 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5+7;
const int logx = 18;
vector<int> G[MAXN];
int jmp[MAXN][logx+1];
int t[MAXN];
int depth[MAXN];
int rep[MAXN];
int val[MAXN];
pair<ll, int> res[MAXN];
int n;

void connect(int a, int b){
	//cout << "connect: " << a << " " << b << "\n";
	G[a].push_back(b);
	G[b].push_back(a);
}

void dfs(int v, int p){
	depth[v] = depth[p] + 1;
	jmp[v][0] = p;
	
	for(int k = 1; k <=logx; k++)
		jmp[v][k] = jmp[jmp[v][k-1]][k-1];
		
	for(auto u : G[v])
		if(u != p) dfs(u, v);

}

int lca(int a, int b){
	if(depth[a] > depth[b]) swap(a, b);
	
	for(int k = logx; k >= 0; k--)
		if(depth[jmp[b][k]] >= depth[a])
			b = jmp[b][k];
			
	if(a == b)
		return a;
	
	for(int k = logx; k >= 0; k--){
		if(jmp[a][k] != jmp[b][k]){
			a = jmp[a][k];
			b = jmp[b][k];
		}
	}
	
	return jmp[a][0];
}

ll get_dist(int a, int b){
	return depth[a] + depth[b] - 2*depth[lca(a, b)];
}

int Find(int a){
	if(rep[a] == a)
		return a;
	return rep[a] = Find(rep[a]);
}

void Union(int a, int b){
	//cout << "a: " << a << " b: " << b << "\n";
	a = Find(a);
	b = Find(b);
	if(a == b) return;
	
	ll dist = get_dist(a, res[b].second);
	pair<ll, int> sum = {res[b].first + dist, a};
	
	
	if(val[a] < val[b]) swap(a, b);
	rep[b] = a;
	val[a] += val[b];
	res[a] = max({res[b], res[a], sum});
}


void merge(int v){

	for(auto u : G[v])
		 if(u < v) Union(v, u);
		 
	//cout << "res: " << v << " " << res[Find(v)].first << "\n";
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	
	for(int i = 1; i <= n; i++)
		cin >> t[i];
	
	for(int i = 1; i < n; i++){
		int a, b;
		cin >> a >> b;
		connect(t[a], t[b]);
	}
	
	dfs(n, n);
	
	for(int i = 1; i <= n; i++){
		rep[i] = i;
		val[i] = 1;
		res[i].second = i;
	}
	
	for(int i = 1; i <= n; i++) merge(i);
	
	cout << res[Find(n)].first << "\n";

}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9692 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Incorrect 159 ms 36140 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

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