Submission #974593

#	Time	Username	Problem	Language	Result	Execution time	Memory
974593		Lecorbio	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	288 ms	48180 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define sajz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 2e5+7, P = 19;
int n, timer = -1, p[N], d[N], tin[N], tout[N], up[N][P]; 
int par[N], sz[N], mx[N], pos[N]; ll dp[N];
vector<int> g[N];

void dfs(int v, int parent){
	tin[v] = ++timer;
	up[v][0] = parent;
	for (int i=1; i<P; i++) up[v][i] = up[up[v][i-1]][i-1];
	for (auto u : g[v]){ 
		if (u == parent) continue;
		d[u] = d[v] + 1;
		dfs(u, v);
	}
	tout[v] = timer;
}

bool ancestor(int a, int b){return tin[a] <= tin[b] && tout[a] >= tout[b];}
int lca(int a, int b){
	if (ancestor(a, b)) return a;
	for (int i=P-1; i>=0; i--){
		if (!ancestor(up[a][i], b)) a = up[a][i];
	}
	return up[a][0];
}

int Find(int a){return a == par[a] ? a : par[a] = Find(par[a]);}
void Union(int a, int b){
	a = Find(a); b = Find(b);
	if (a != b){
		if (sz[a] < sz[b]) swap(a, b);
		sz[a] += sz[b];
		par[b] = a;
		mx[a] = max(mx[a], mx[b]);
	}
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    vector<pair<int,int>> sorted;
    for (int i=1; i<=n; i++){ 
		cin >> p[i];
		sz[i] = 1;
		par[i] = i;
		mx[i] = p[i];
		pos[p[i]] = i;
		sorted.push_back({p[i], i});
	}
	sort(all(sorted));
    for (int i=0; i<n-1; i++){
		int a, b; cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	dfs(1, 1);
	
	for (auto [val, v] : sorted){
		for (auto u : g[v]){
			if (p[u] < val){
				int x = pos[mx[Find(u)]];
				ll dist = d[v] + d[x] - 2 * d[lca(v, x)];
				dp[v] = max(dp[v], dp[x] + dist);
				Union(v, u);
			}
		}
		if (val == n){cout << dp[v] << '\n'; return 0;}
	}
 
    return 0;
}
/*

4
3 4 1 2
1 2
2 3
3 4

*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:70:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |  for (auto [val, v] : sorted){
      |            ^

• 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