Submission #1263582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263582		kustov_vadim_533	Cat Exercise (JOI23_ho_t4)	C++20	31 / 100	2093 ms	24644 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#define len(v) (int)((v).size())

template<typename T>
ostream& operator<<(ostream& out, const vector<T> &a){
	for  (auto& x : a){
		out << x << ' ';
	}
	out << '\n';
	return out;
}

template<typename T>
istream& operator>>(istream& in, vector<T> &a){
	for (size_t i = 0; i < a.size(); ++i){
		in >> a[i];
	}
	return in;
}

mt19937 gen;

const int N = 2e5 + 7;
vector<int> g[N];
int a[N];
bool us[N];

pair<int, int> dfs2(int v, int p){
	pair<int, int> res = {v, 0};

	for (int u : g[v]){
		if (u == p) continue;
		if (us[u]) continue;

		pair<int, int> r = dfs2(u, v);
		r.second++;
		if (a[r.first] > a[res.first]) res = r;
	}
	return res;
}

int dfs(int v){
	pair<int, int> cf = dfs2(v, v);
	v = cf.first;

	int res = 0;

	us[v] = true;
	for (int u : g[v]){
		if (!us[u]){
			res = max(res, dfs(u));
		}
	}
	us[v] = false;

	return res + cf.second + 1;
}

inline void solve() {
	int n;
	cin >> n;

	for (int i = 0; i < n; ++i){
		cin >> a[i];
		us[i] = false;
	}

	for (int i = 0; i < n - 1; ++i){
		int x, y;
		cin >> x >> y;
		g[--x].push_back(--y);
		g[y].push_back(x);
	}

	int ans = 0;
	for (int i = 0; i < n; ++i){
		if (a[i] == n){
			ans = dfs(i);
		}
	}
	cout << ans - 1 << '\n';
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout.precision(60);

	int t = 1;
//	cin >> t;

	while (t--) {
		solve();
	}
}

• 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