Submission #1032007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032007		ten_xd	Cat Exercise (JOI23_ho_t4)	C++17	54 / 100	2029 ms	47440 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, 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;

void DFS(int v, int par)
{
	//cout << "K: " << v << '\n';
	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 odl(int a, int b)
{
	int res = 0;
	while(a != b)
	{
		++res;
		if(deg[a] > deg[b]) a = P[a];
		else b = P[b];
	}
	return res;
}

//int cm= 0;
ll DFS2(int v, int b)
{
	//++cm;
	//if(cm >= 8) return 0;
	//cout << "V: " << v << " B: " << b << '\n';
	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);
			//cout << "VV: " << v << " XX: " << x << " AKT V: " << akt.v << " AKT VAL: " << akt.val << '\n';
			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);
		//cout << "VVVVV: " << v << " AKT V: " << akt.v << " AKT VAL: " << akt.val << '\n';
		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]);

	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: 0 / 20
• Subtask 6: 23 / 23
• Subtask 7: 0 / 26