Submission #1085814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085814		I_am_Polish_Girl	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	336 ms	81600 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 <vector <int>> g;

vector <int> t_in;
vector <int> t_out;

vector <vector <int>> bin;

vector <int> deep;

vector <int> a;

int t = 0;

void dfs_build(int ind, int last , int d)
{
	deep[ind] = d;

	bin[ind][0] = last;

	for (int i = 1; i < log_; i++)
	{
		bin[ind][i] = bin[bin[ind][i - 1]][i - 1];
	}

	t_in[ind] = t;
	t++;

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

		if (ind_s == last)
			continue;

		dfs_build(ind_s, ind , d+1);
	}

	t_out[ind] = t;
	t++;
}

bool is_up(int u, int v)
{
	if ((t_in[u] <= t_in[v]) and (t_out[v] <= t_out[u]))
	{
		return true;
	}

	return false;
}

int lca(int u, int v)
{
	if (is_up(u, v) == true)
		return u;

	if (is_up(v , u) == true)
		return v;

	for (int i = log_ - 1; i >= 0; i--)
	{
		int u_ = bin[u][i];

		if (is_up(u_, v) == false)
			u = u_;
	}

	u = bin[u][0];
	return u;
}

int dist(int u, int v)
{
	int l = lca(u, v);

	return deep[u] + deep[v] - 2 * deep[l];
}


vector <int> link;
vector <int> w;
vector <int> ind_;

int per(int u)
{
	if (link[u] == u)
		return u;

	link[u] = per(link[u]);

	return link[u];
}

void merge(int u, int v)
{
	u = per(u);
	v = per(v);

	if (u == v)
		return;

	if (w[u] < w[v])
		swap(u, v);


	link[v] = u;
	w[u] += w[v];

	if (a[ind_[u]] < a[ind_[v]])
		ind_[u] = ind_[v];
}


vector <int> dp;



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

	int n;
	cin >> n;


	link.resize(n);
	w.resize(n);
	ind_.resize(n);

	for (int i = 0; i < n; i++)
	{
		link[i] = i;
		w[i] = 1;
		ind_[i] = i;
	}

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

	t_in.resize(n);
	t_out.resize(n);

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

	bin.resize(n);

	for (int i = 0; i < n; i++)
	{
		bin[i].resize(log_);
	}


	deep.resize(n);


	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);
	}


	dfs_build(0, 0, 0);

	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 k = 0; k < n; k++)
	{
		int ind = vp[k].second;

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

			if (dp[ind_s] != -1)
			{
				int u = ind_[per(ind_s)];

				dp[ind] = max(dp[ind], dist(ind, u) + dp[u]);
			}
		}

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

			if (dp[ind_s] != -1)
			{
				merge(ind, ind_s);
			}
		}


		dp[ind] = max(dp[ind], 0ll);
	}


	for (int i = 0; i < n; i++)
		if (a[i] == n)
			cout << dp[i];
}

/*
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_build(long long int, long long int, long long int)':
Main.cpp:62: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]
   62 |  for (int i = 0; i < g[ind].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:224:21: 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]
  224 |   for (int i = 0; i < g[ind].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~
Main.cpp:236:21: 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]
  236 |   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: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26