답안 #1031952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1031952	2024-07-23T09:03:58 Z	ten_xd	Cat Exercise (JOI23_ho_t4)	C++17	31 / 100	2000 ms	35288 KB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back

const int N = 5e5+5, INF = 2e9+54321;
const ll INF_L = (ll)2e18+54321;

int n,wie,mx,odl,nrw;
int A[N];
vector<int> G[N];
bool vis[N];

void DFS2(int v, int par, int di)
{
	mx = max(mx,A[v]);
	if(mx == A[v]) odl = di, nrw = v;
	for(auto x : G[v])
	{
		if(x == par or vis[x]) continue;
		DFS2(x,v,di+1);
	}
}

ll DFS(int v)
{
	//cout << "VV: " << v << '\n';
	vis[v] = 1;
	ll val = 0;
	for(auto x : G[v])
	{
		mx = -1, odl = 0;
		if(!vis[x])
		{
			DFS2(x,v,1);
			val = max(val,odl+DFS(nrw));
		}
	}
	//cout << "V: " << v << " VAL: " << val << '\n';
	return val;
}

void solve()
{
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> A[i];
	rep(i,n-1)
	{
		int a,b;
		cin >> a >> b;
		G[a].pb(b), G[b].pb(a);
	}

	for(int i = 1; i <= n; ++i) if(A[i] == n) wie = i;
	cout << DFS(wie) << '\n';
}

int main()
{	
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int T = 1;
	//cin >> T;
	while(T--) solve();

	return 0;
}

Subtask #1

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	12124 KB	Output is correct
2	Correct	4 ms	12124 KB	Output is correct
3	Correct	6 ms	12124 KB	Output is correct
4	Correct	5 ms	12212 KB	Output is correct
5	Correct	5 ms	12124 KB	Output is correct
6	Correct	5 ms	12208 KB	Output is correct
7	Correct	5 ms	12124 KB	Output is correct
8	Correct	5 ms	12120 KB	Output is correct
9	Correct	6 ms	12124 KB	Output is correct
10	Correct	5 ms	12124 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	12124 KB	Output is correct
2	Correct	4 ms	12124 KB	Output is correct
3	Correct	6 ms	12124 KB	Output is correct
4	Correct	5 ms	12212 KB	Output is correct
5	Correct	5 ms	12124 KB	Output is correct
6	Correct	5 ms	12208 KB	Output is correct
7	Correct	5 ms	12124 KB	Output is correct
8	Correct	5 ms	12120 KB	Output is correct
9	Correct	6 ms	12124 KB	Output is correct
10	Correct	5 ms	12124 KB	Output is correct
11	Correct	5 ms	12124 KB	Output is correct
12	Correct	5 ms	12124 KB	Output is correct
13	Correct	5 ms	12216 KB	Output is correct
14	Correct	5 ms	12124 KB	Output is correct
15	Correct	5 ms	12124 KB	Output is correct
16	Correct	5 ms	12124 KB	Output is correct
17	Correct	5 ms	12124 KB	Output is correct

Subtask #3

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	12124 KB	Output is correct
2	Correct	4 ms	12124 KB	Output is correct
3	Correct	6 ms	12124 KB	Output is correct
4	Correct	5 ms	12212 KB	Output is correct
5	Correct	5 ms	12124 KB	Output is correct
6	Correct	5 ms	12208 KB	Output is correct
7	Correct	5 ms	12124 KB	Output is correct
8	Correct	5 ms	12120 KB	Output is correct
9	Correct	6 ms	12124 KB	Output is correct
10	Correct	5 ms	12124 KB	Output is correct
11	Correct	5 ms	12124 KB	Output is correct
12	Correct	5 ms	12124 KB	Output is correct
13	Correct	5 ms	12216 KB	Output is correct
14	Correct	5 ms	12124 KB	Output is correct
15	Correct	5 ms	12124 KB	Output is correct
16	Correct	5 ms	12124 KB	Output is correct
17	Correct	5 ms	12124 KB	Output is correct
18	Correct	86 ms	12636 KB	Output is correct
19	Correct	76 ms	12748 KB	Output is correct
20	Correct	75 ms	12632 KB	Output is correct
21	Correct	6 ms	12632 KB	Output is correct
22	Correct	6 ms	12448 KB	Output is correct
23	Correct	7 ms	12636 KB	Output is correct
24	Correct	6 ms	12380 KB	Output is correct

Subtask #4

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	12124 KB	Output is correct
2	Correct	4 ms	12124 KB	Output is correct
3	Correct	6 ms	12124 KB	Output is correct
4	Correct	5 ms	12212 KB	Output is correct
5	Correct	5 ms	12124 KB	Output is correct
6	Correct	5 ms	12208 KB	Output is correct
7	Correct	5 ms	12124 KB	Output is correct
8	Correct	5 ms	12120 KB	Output is correct
9	Correct	6 ms	12124 KB	Output is correct
10	Correct	5 ms	12124 KB	Output is correct
11	Correct	5 ms	12124 KB	Output is correct
12	Correct	5 ms	12124 KB	Output is correct
13	Correct	5 ms	12216 KB	Output is correct
14	Correct	5 ms	12124 KB	Output is correct
15	Correct	5 ms	12124 KB	Output is correct
16	Correct	5 ms	12124 KB	Output is correct
17	Correct	5 ms	12124 KB	Output is correct
18	Correct	86 ms	12636 KB	Output is correct
19	Correct	76 ms	12748 KB	Output is correct
20	Correct	75 ms	12632 KB	Output is correct
21	Correct	6 ms	12632 KB	Output is correct
22	Correct	6 ms	12448 KB	Output is correct
23	Correct	7 ms	12636 KB	Output is correct
24	Correct	6 ms	12380 KB	Output is correct
25	Correct	5 ms	12212 KB	Output is correct
26	Correct	87 ms	12672 KB	Output is correct
27	Correct	88 ms	12632 KB	Output is correct
28	Correct	85 ms	12632 KB	Output is correct
29	Correct	83 ms	12632 KB	Output is correct
30	Correct	9 ms	12376 KB	Output is correct
31	Correct	11 ms	12256 KB	Output is correct
32	Correct	10 ms	12472 KB	Output is correct
33	Correct	10 ms	12380 KB	Output is correct

Subtask #5

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	12124 KB	Output is correct
2	Correct	4 ms	12124 KB	Output is correct
3	Correct	6 ms	12124 KB	Output is correct
4	Correct	5 ms	12212 KB	Output is correct
5	Correct	5 ms	12124 KB	Output is correct
6	Correct	5 ms	12208 KB	Output is correct
7	Correct	5 ms	12124 KB	Output is correct
8	Correct	5 ms	12120 KB	Output is correct
9	Correct	6 ms	12124 KB	Output is correct
10	Correct	5 ms	12124 KB	Output is correct
11	Correct	5 ms	12124 KB	Output is correct
12	Correct	5 ms	12124 KB	Output is correct
13	Correct	5 ms	12216 KB	Output is correct
14	Correct	5 ms	12124 KB	Output is correct
15	Correct	5 ms	12124 KB	Output is correct
16	Correct	5 ms	12124 KB	Output is correct
17	Correct	5 ms	12124 KB	Output is correct
18	Correct	86 ms	12636 KB	Output is correct
19	Correct	76 ms	12748 KB	Output is correct
20	Correct	75 ms	12632 KB	Output is correct
21	Correct	6 ms	12632 KB	Output is correct
22	Correct	6 ms	12448 KB	Output is correct
23	Correct	7 ms	12636 KB	Output is correct
24	Correct	6 ms	12380 KB	Output is correct
25	Execution timed out	2061 ms	35288 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-

Subtask #6

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	12120 KB	Output is correct
2	Correct	5 ms	12028 KB	Output is correct
3	Execution timed out	2024 ms	23164 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #7

0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	12124 KB	Output is correct
2	Correct	4 ms	12124 KB	Output is correct
3	Correct	6 ms	12124 KB	Output is correct
4	Correct	5 ms	12212 KB	Output is correct
5	Correct	5 ms	12124 KB	Output is correct
6	Correct	5 ms	12208 KB	Output is correct
7	Correct	5 ms	12124 KB	Output is correct
8	Correct	5 ms	12120 KB	Output is correct
9	Correct	6 ms	12124 KB	Output is correct
10	Correct	5 ms	12124 KB	Output is correct
11	Correct	5 ms	12124 KB	Output is correct
12	Correct	5 ms	12124 KB	Output is correct
13	Correct	5 ms	12216 KB	Output is correct
14	Correct	5 ms	12124 KB	Output is correct
15	Correct	5 ms	12124 KB	Output is correct
16	Correct	5 ms	12124 KB	Output is correct
17	Correct	5 ms	12124 KB	Output is correct
18	Correct	86 ms	12636 KB	Output is correct
19	Correct	76 ms	12748 KB	Output is correct
20	Correct	75 ms	12632 KB	Output is correct
21	Correct	6 ms	12632 KB	Output is correct
22	Correct	6 ms	12448 KB	Output is correct
23	Correct	7 ms	12636 KB	Output is correct
24	Correct	6 ms	12380 KB	Output is correct
25	Correct	5 ms	12212 KB	Output is correct
26	Correct	87 ms	12672 KB	Output is correct
27	Correct	88 ms	12632 KB	Output is correct
28	Correct	85 ms	12632 KB	Output is correct
29	Correct	83 ms	12632 KB	Output is correct
30	Correct	9 ms	12376 KB	Output is correct
31	Correct	11 ms	12256 KB	Output is correct
32	Correct	10 ms	12472 KB	Output is correct
33	Correct	10 ms	12380 KB	Output is correct
34	Execution timed out	2061 ms	35288 KB	Time limit exceeded
35	Halted	0 ms	0 KB	-