Submission #1241225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241225		nai0610	Cat Exercise (JOI23_ho_t4)	C++20	31 / 100	6 ms	3656 KiB

Main

#include <bits/stdc++.h>
#define ll int64_t
#define ld long double
using namespace std;
// 
const int maxn =1e5+5;
const int mod = 1e9+7; // 998244353,1610612741
const ll inf = 1e18;
const ld pi = atan(1.0L)*4;
int n,p[maxn],par[maxn];
vector<int> g[maxn];
int h[maxn],st[maxn][20];
ll f[maxn];
int find(int u) {
	return (u==par[u]?u:par[u]=find(par[u]));
}
void dfs2(int u){
	for (auto v:g[u]) {
		if (st[u][0]==v) continue;
		h[v]=h[u]+1;
		st[v][0]=u;
		for (int i=1;i<=17;i++) st[v][i]=st[st[v][i-1]][i-1];
		dfs2(v);
	}
}
int calc(int u,int k){
	for (int i=0;(1<<i)<=k;i++) {
		if (k&(1<<i)) u=st[u][i];
	}
	return u;
}
int lca(int u,int v){
	if (h[u]!=h[v]) {
		if (h[u]<h[v]) swap(u,v);
		u=calc(u,h[u]-h[v]);
	}
	if (u==v) return u;
	for (int i=__lg(h[u]);i>=0;i--){
		if (st[u][i]!=st[v][i]){
			u=st[u][i];
			v=st[v][i];
		}
	}
	return st[u][0];
}
int dist(int u,int v) {
	int lc=lca(u,v);
	return h[u]+h[v]-2*h[lc];
}
int main() {
    // freopen("../input.inp","r",stdin);
    // freopen("output.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    clock_t start,end;
	start=clock();
	cin >>n;
	for (int i=1;i<=n;i++) cin >>p[i],par[i]=i;
	for (int i=1;i<n;i++) {
		int u,v;
		cin >>u>>v;
		u=p[u];v=p[v];
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs2(1);
	for (int i=1;i<=n;i++) {
		for (auto j:g[i]) {
			if (j<i) {
				int u=find(j);
				f[i]=max(f[i],f[u]+dist(i,u));
				par[u]=i;
			}
		}
	}
	cout <<*max_element(f+1,f+1+n);
	end=clock();
	ld dur=(ld)(end-start)/(ld)(CLOCKS_PER_SEC)*(1000.0L);
	cerr<<dur<<'\n';
    return 0;
}

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