Submission #1059299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059299		beaconmc	Cat Exercise (JOI23_ho_t4)	C++14	31 / 100	2085 ms	51028 KiB

Main

#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;
const ll maxn = 200005;

ll vals[maxn];

bool visited[maxn];
vector<ll> edges[maxn];
ll root = 0;


ll ans = 0;

vector<ll> dfs2(ll a, ll p){
	vector<ll> ans = {a,0};
	for (auto&i : edges[a]){
		if (!visited[i] && i != p){
			vector<ll> node = dfs2(i, a);
			node[1]++;
			if (vals[ans[0]] < vals[node[0]]) ans = node;

		}
	}
	return ans;
}
void dfs(ll a, ll dist){
	//cout << a << " "<<dist << endl;
	ans = max(ans, dist);
	for (auto&i : edges[a]){
		if (!visited[i]){
			vector<ll> node = dfs2(i, a);
			visited[node[0]] = 1;
			dfs(node[0], dist+node[1]+1);
		}
	}
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n;
	cin >> n;
	FOR(i,0,n) cin >> vals[i];
	FOR(i,0,n-1){
		ll a,b;
		cin >> a >> b;
		a--;b--;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}

	FOR(i,0,n){
		if (vals[i] == n){
			visited[i] = 1;
			dfs(i,0);
		}
	}
	cout << ans << endl;


}

• 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