Submission #1285734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285734		tunademayo	Cat Exercise (JOI23_ho_t4)	C++20	31 / 100	520 ms	99500 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define ll long long 

const bool Multitest = 0;

const int N = 2e5 + 10;

int a[N], n; vector<int> adj[N];

namespace trau
{
	const int M = 5005;
	vector<pair<int, int>> g[N];
	bool check() 
	{
		return n <= 5000;
	}
	
	int f[M][M]; 
	bool vis[N];
	
	void dfs(int u, int p, int p1)
	{
		f[p1][u] = f[p1][p] + 1;
		for(int v : adj[u]) if(v != p)
		{
			dfs(v, u, p1);			
		}
	}
	
	int dp[N];
	
	void dfs(int u, int p)
	{
		for(auto [v, w] : g[u]) if(v != p)
		{
			dfs(v, u);
			dp[u] = max(dp[v] + w, dp[u]);
		}
	}
	
	int find(int u, int p)
	{
		int ans = u;
		
		for(int v : adj[u]) if(v != p && vis[v] == 0)
		{
			int x = find(v, u);
			
			if(a[ans] < a[x]) ans = x;
		}
		
		return ans;
	}
	
	void comp(int u)
	{
		vis[u] = 1;
		for(int v : adj[u]) if(vis[v] == 0)
		{
			int x = find(v, u);
			
			g[a[u]].push_back({a[x], f[u][x]});
			g[a[x]].push_back({a[u], f[u][x]});
			
			comp(x);
		}
	}
	
	void solve()
	{
		
		for(int i = 1 ; i <= n ; i++)
		{
			f[i][0] = -1;
			dfs(i, 0, i);
		}
	
		for(int i = 1 ; i <= n ; i++) if(a[i] == n) comp(i);
		dfs(n, 0);
		
		cout << dp[n];
	}
}

void work()
{
	cin >> n;
	
	for(int i = 1 ; i <= n ; i++) cin >> a[i];
	
	for(int i = 1 ; i < n ; i++) 
	{
		int u, v;	cin >> u >> v;
		
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	if(trau::check()) 
	{
		trau::solve();
		
		return;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);
	
	int q = 1;
	
	if(Multitest)	cin >> q;
	
	while(q--) work();
}

• 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