Submission #1032010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032010		ten_xd	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	239 ms	62544 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back

const int N = 5e5+5, LG = 18, INF = 2e9+54321;
const ll INF_L = (ll)2e18+54321;

struct Node
{
	int v, val;
	bool operator < (const Node &node) const
	{
		return val < node.val;
	}
};

int n,cnt,base,rozmiar_drzewa;
int A[N];
vector<int> G[N];
bool vis[N];
int pre[N];
int siz[N];
int P[N];
int deg[N];
vector<Node> tree;
int skok[LG+1][N];

void DFS(int v, int par)
{
	siz[v] = 1, pre[v] = ++cnt, P[v] = par, tree[cnt+base] = {v,A[v]};
	for(auto x : G[v])
	{
		if(x == par) continue;
		deg[x] = deg[v] + 1, DFS(x,v), siz[v] += siz[x];
	}
}

Node query(int l, int p)
{
	l = l + base - 1, p = p + base + 1;
	Node res = {-1,-1};
	while(l/2 != p/2)
	{
		if(l % 2 == 0) res = max(res,tree[l+1]);
		if(p % 2 == 1) res = max(res,tree[p-1]);
		l /= 2, p /= 2;
	}
	return res;
}

void update(int v, Node val)
{
	v += base, tree[v] = val, v /= 2;
	while(v > 0) tree[v] = max(tree[v*2],tree[v*2+1]), v /= 2;
}

int LCA(int x, int y)
{
	if(deg[x] < deg[y]) swap(x,y);
	for(int i = LG; i >= 0; --i)
	{
		int v = skok[i][x];
		if(deg[v] >= deg[y]) x = v;
	}

	if(x == y) return x;
	for(int i = LG; i >= 0; --i)
	{
		int vx = skok[i][x], vy = skok[i][y];
		if(vx != vy) x = vx, y = vy;
	}
	return skok[0][x];
}

int odl(int a, int b)
{
	return deg[a] + deg[b] - 2*deg[LCA(a,b)];
}

ll DFS2(int v, int b)
{
	vis[v] = 1;
	ll val = 0;
	update(pre[v],{-1,-1});
	for(auto x : G[v])
	{
		if(vis[x]) continue;
		if(deg[x] > deg[v])
		{
			Node akt = query(pre[x],pre[x]+siz[x]-1);
			val = max(val,(ll)odl(v,akt.v)+DFS2(akt.v,x));
		}
	}
	if(v != b)
	{
		Node akt = query(pre[b],pre[b]+siz[b]-1);
		val = max(val,(ll)odl(v,akt.v)+DFS2(akt.v,b));
	}
	return val;
}

void solve()
{
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> A[i];
	rep(i,n-1)
	{
		int a,b;
		cin >> a >> b;
		G[a].pb(b), G[b].pb(a);
	}

	base = 1;
	while(base <= n+5) base *= 2;
	rozmiar_drzewa = base * 2;
	tree.assign(rozmiar_drzewa,{-1,-1});

	deg[1] = 1, DFS(1,0);
	for(int i = base-1; i >= 1; --i) tree[i] = max(tree[i*2],tree[i*2+1]);

	for(int i = 1; i <= n; ++i) skok[0][i] = P[i];
	for(int i = 1; i <= LG; ++i) for(int v = 1; v <= n; ++v) skok[i][v] = skok[i-1][skok[i-1][v]];

	int wie = 1;
	for(int i = 1; i <= n; ++i) if(A[i] == n) wie = i;
	cout << DFS2(wie,1) << '\n';
}

int main()
{	
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int T = 1;
	//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