Submission #1085803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085803		I_am_Polish_Girl	Cat Exercise (JOI23_ho_t4)	C++14	31 / 100	2096 ms	23820 KiB

Main

#pragma target("arch=icelake-server")

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack> 
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <bitset>

using namespace std;

#define int long long 

typedef long long ll;
typedef long double ld;

int log_ = 21;
int inf = 1000000007;

long long mod = 998244353;

int p = 499;

int NADIYA = 39;

vector <int> dp;

vector <vector <int>> g;
vector <int> a;

int mx = -1;
int mx2 = -1;


void dfs(int ind , int last , int d)
{
	if (last != -1)
	{
		if (mx2 < a[ind])
		{
			mx = max(dp[ind] + d , mx);

			mx2 = a[ind];
		}
	}

	for (int i = 0; i < g[ind].size(); i++)
	{
		int ind_s = g[ind][i];

		if (ind_s == last)
			continue;

		if (dp[ind_s] == -1)
			continue;

		dfs(ind_s, ind , d+1);

		if (last == -1)
			mx2 = -1;
	}
}

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

	int n;
	cin >> n;

	dp.resize(n, -1);
	a.resize(n);

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

	g.resize(n);

	for (int i = 0; i < n - 1; i++)
	{
		int u, v;
		cin >> u >> v;
		
		u--;
		v--;

		g[u].push_back(v);
		g[v].push_back(u);
	}

	vector <pair <int, int>> vp;

	for (int i = 0; i < n; i++)
	{
		vp.push_back({ a[i] , i });
	}

	sort(vp.begin(), vp.end());

	
	for (int i = 0; i < n; i++)
	{
		mx = -1; 
		mx2 = -1;

		int ind = vp[i].second;

		dfs(ind, -1 , 0);

		mx = max(mx, 0ll);

		dp[ind] = mx;
	}

	cout << mx;
}

/*
5 5 2
2 2
4 4
#....
#.##.
####.
##...
.....
*/

Compilation message (stderr)

Main.cpp:1: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    1 | #pragma target("arch=icelake-server")
      | 
Main.cpp: In function 'void dfs(long long int, long long int, long long int)':
Main.cpp:55:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for (int i = 0; i < g[ind].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~

• 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