oj.uz

Submission #1085813

# Submission time Handle Problem Language Result Execution time Memory
1085813 2024-09-08T18:22:40 Z I_am_Polish_Girl Cat Exercise (JOI23_ho_t4) C++14
41 / 100
 196 ms 83544 KB 
#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 = link[u];
	v = link[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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 596 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 596 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 408 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 596 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 408 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 3 ms 2392 KB Output is correct
19 Correct 3 ms 2396 KB Output is correct
20 Correct 3 ms 2396 KB Output is correct
21 Correct 4 ms 2396 KB Output is correct
22 Correct 3 ms 2396 KB Output is correct
23 Correct 4 ms 2464 KB Output is correct
24 Correct 3 ms 2392 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 596 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 408 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 3 ms 2392 KB Output is correct
19 Correct 3 ms 2396 KB Output is correct
20 Correct 3 ms 2396 KB Output is correct
21 Correct 4 ms 2396 KB Output is correct
22 Correct 3 ms 2396 KB Output is correct
23 Correct 4 ms 2464 KB Output is correct
24 Correct 3 ms 2392 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 4 ms 2396 KB Output is correct
27 Correct 4 ms 2392 KB Output is correct
28 Correct 8 ms 2396 KB Output is correct
29 Correct 3 ms 2328 KB Output is correct
30 Incorrect 4 ms 2136 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 596 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 408 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 3 ms 2392 KB Output is correct
19 Correct 3 ms 2396 KB Output is correct
20 Correct 3 ms 2396 KB Output is correct
21 Correct 4 ms 2396 KB Output is correct
22 Correct 3 ms 2396 KB Output is correct
23 Correct 4 ms 2464 KB Output is correct
24 Correct 3 ms 2392 KB Output is correct
25 Correct 142 ms 83544 KB Output is correct
26 Correct 138 ms 83392 KB Output is correct
27 Correct 140 ms 83396 KB Output is correct
28 Correct 152 ms 83392 KB Output is correct
29 Correct 189 ms 83420 KB Output is correct
30 Correct 155 ms 83408 KB Output is correct
31 Correct 153 ms 83528 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 196 ms 72384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 596 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 408 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 3 ms 2392 KB Output is correct
19 Correct 3 ms 2396 KB Output is correct
20 Correct 3 ms 2396 KB Output is correct
21 Correct 4 ms 2396 KB Output is correct
22 Correct 3 ms 2396 KB Output is correct
23 Correct 4 ms 2464 KB Output is correct
24 Correct 3 ms 2392 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 4 ms 2396 KB Output is correct
27 Correct 4 ms 2392 KB Output is correct
28 Correct 8 ms 2396 KB Output is correct
29 Correct 3 ms 2328 KB Output is correct
30 Incorrect 4 ms 2136 KB Output isn't correct
31 Halted 0 ms 0 KB -