Submission #758883

#	Time	Username	Problem	Language	Result	Execution time	Memory
758883		PoPularPlusPlus	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	294 ms	50228 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

bool remender(ll a , ll b){return a%b;}

const int N = 200003 , L = 20;

struct dsu {
	vector<int> p , siz , mn;
	
	void init(vector<int> a){
		int n = a.size();
		p.resize(n);
		siz.resize(n);
		mn.resize(n);
		for(int i = 0; i < n; i++){
			p[i] = i;
			siz[i] = 1;
			mn[i] = a[i];
		}
	}
	
	int get(int x){
		return p[x] = (p[x] == x ? x : get(p[x]));
	}
	
	void unio(int x , int y){
		x = get(x);
		y = get(y);
		if(x == y)return;
		if(siz[x] > siz[y]){
			swap(x,y);
		}
		p[x] = y;
		siz[y] += siz[x];
		mn[y] = max(mn[y],mn[x]);
	}
};

vector<int> adj[N];

int timer,tin[N],tout[N],up[N][L],depth[N];

void dfs(int node , int par){
	tin[node] = timer++;
	up[node][0] = par;
	for(int i = 1; i < L; i++){
		up[node][i] = up[up[node][i-1]][i-1];
	}
	for(int i : adj[node]){
		if(i!=par){
			depth[i] = depth[node] + 1;
			dfs(i,node);
		}
	}
	tout[node] = timer++;
}

bool is_lca(int x , int y){
	return tin[x] <= tin[y] && tout[x] >= tout[y];
}

int find(int x , int y){
	if(is_lca(x,y))return x;
	if(is_lca(y,x))return y;
	for(int i = L-1; i >= 0; i--){
		if(!is_lca(up[x][i],y))x = up[x][i];
	}
	return up[x][0];
}

int dis(int u , int v){
	int lca = find(u , v);
	return depth[u] + depth[v] - 2 * depth[lca];
}

void solve(){
	int n;
	cin >> n;
	vector<int> arr(n + 1);
	arr[0] = 0;
	int pos[n + 1];
	for(int i = 1; i <= n; i++){
		cin >> arr[i];
		pos[arr[i]] = i;
	}
	for(int i = 0; i < n - 1; i++){
		int u , v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	
	timer = 0;
	depth[1] = 0;
	dfs(1,1);
	
	dsu d;
	d.init(arr);
	ll ans[n + 1];
	ans[1] = 0;
	for(int i = 2; i <= n; i++){
		ans[i] = 0;
		int node = pos[i];
		for(int j : adj[node]){
			if(arr[j] < i){
				//cout << dis(node , pos[d.mn[d.get(j)]]) << ' ' << pos[d.mn[d.get(j)]] << ' ';
				//cout << dis(node,d.mn[d.get(j)]) << ' ' << d.mn[d.get(j)] << ' ';
				ans[i] = max(ans[i] , dis(node,pos[d.mn[d.get(j)]]) + ans[d.mn[d.get(j)]]);
				d.unio(j , node);
			}
		}
		//cout << ans[i] << ' ';
	}
	cout << ans[n] << '\n';
}

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("deleg.in", "r", stdin);
//freopen("deleg.out", "w", stdout);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

• 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