답안 #1085803

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1085803 2024-09-08T18:02:08 Z I_am_Polish_Girl Cat Exercise (JOI23_ho_t4) C++14
31 / 100
2000 ms 23820 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 <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

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++)
      |                  ~~^~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 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 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 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 348 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 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 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 348 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 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 94 ms 1192 KB Output is correct
19 Correct 86 ms 1364 KB Output is correct
20 Correct 87 ms 1224 KB Output is correct
21 Correct 3 ms 1116 KB Output is correct
22 Correct 2 ms 1116 KB Output is correct
23 Correct 3 ms 1116 KB Output is correct
24 Correct 2 ms 1116 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 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 348 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 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 94 ms 1192 KB Output is correct
19 Correct 86 ms 1364 KB Output is correct
20 Correct 87 ms 1224 KB Output is correct
21 Correct 3 ms 1116 KB Output is correct
22 Correct 2 ms 1116 KB Output is correct
23 Correct 3 ms 1116 KB Output is correct
24 Correct 2 ms 1116 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 118 ms 1220 KB Output is correct
27 Correct 105 ms 1112 KB Output is correct
28 Correct 103 ms 1208 KB Output is correct
29 Correct 97 ms 1144 KB Output is correct
30 Correct 7 ms 1112 KB Output is correct
31 Correct 11 ms 1036 KB Output is correct
32 Correct 8 ms 1116 KB Output is correct
33 Correct 9 ms 1124 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 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 348 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 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 94 ms 1192 KB Output is correct
19 Correct 86 ms 1364 KB Output is correct
20 Correct 87 ms 1224 KB Output is correct
21 Correct 3 ms 1116 KB Output is correct
22 Correct 2 ms 1116 KB Output is correct
23 Correct 3 ms 1116 KB Output is correct
24 Correct 2 ms 1116 KB Output is correct
25 Execution timed out 2071 ms 22816 KB Time limit exceeded
26 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 2096 ms 23820 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 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 348 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 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 94 ms 1192 KB Output is correct
19 Correct 86 ms 1364 KB Output is correct
20 Correct 87 ms 1224 KB Output is correct
21 Correct 3 ms 1116 KB Output is correct
22 Correct 2 ms 1116 KB Output is correct
23 Correct 3 ms 1116 KB Output is correct
24 Correct 2 ms 1116 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 118 ms 1220 KB Output is correct
27 Correct 105 ms 1112 KB Output is correct
28 Correct 103 ms 1208 KB Output is correct
29 Correct 97 ms 1144 KB Output is correct
30 Correct 7 ms 1112 KB Output is correct
31 Correct 11 ms 1036 KB Output is correct
32 Correct 8 ms 1116 KB Output is correct
33 Correct 9 ms 1124 KB Output is correct
34 Execution timed out 2071 ms 22816 KB Time limit exceeded
35 Halted 0 ms 0 KB -