답안 #1059373

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1059373	2024-08-14T22:01:14 Z	beaconmc	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	376 ms	101200 KB

Main

#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;
const ll maxn = 200005;

ll vals[maxn];
ll which[maxn+2];

bool visited[maxn];
vector<ll> edges[maxn];
vector<vector<ll>> edges2[maxn];


ll cmp[maxn];
ll maxis[maxn];



ll ancc[maxn][30];
ll depth[maxn];
ll par[maxn];

ll anc(ll a, ll x){
	if (a==0) return 0;
	if (x==0) return par[a];
	if (ancc[a][x] != -1) return ancc[a][x];

	return ancc[a][x] = anc(anc(a,x-1),x-1);
}

ll lca(ll a, ll b){
	if (depth[a] < depth[b]) swap(a,b);
	FORNEG(i,29,-1) if (depth[anc(a,i)] >= depth[b]) a = anc(a,i);
	if (a==b) return a;
	FORNEG(i,29,-1) if (anc(a,i) != anc(b,i)) a = anc(a,i), b = anc(b,i);
	return par[a];
}


void initdfs(ll a, ll p, ll d){
	depth[a] = d;
	par[a] = p;
	for (auto&i : edges[a]) if (i != p) initdfs(i, a, d+1);
}

ll find(ll a){
	while (a != cmp[a]){
		cmp[a] = cmp[cmp[a]];
		a = cmp[a];
	}
	return a;
}
void unite(ll a, ll b){
	ll A = find(a);
	ll B = find(b);

	maxis[B] = max(maxis[B], maxis[A]);
	cmp[A] = B;
}



ll dp(ll a, ll p){
	ll ans = 0;
	for (auto&i : edges2[a]){
		if (i[0] != p) ans = max(ans, dp(i[0], a) + i[1]);
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n;
	cin >> n;
	FOR(i,0,maxn) cmp[i] = i, maxis[i] = -1;
	FOR(i,0,maxn) FOR(j,0,30) ancc[i][j] = -1;

	FOR(i,0,n){
		cin >> vals[i];
		which[vals[i]] = i;
		maxis[find(i)] = vals[i];
	}
	FOR(i,0,n-1){
		ll a,b;
		cin >> a >> b;
		a--;b--;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}

	initdfs(0,-1,0);



	FOR(i,1,n+1){
		ll root = which[i];

		for (auto&i : edges[root]){
			if (vals[i] > vals[root]) continue;
			ll maxi = which[maxis[find(i)]];

			edges2[root].push_back({maxi, depth[root]+depth[maxi] - 2*depth[lca(root, maxi)]});
			unite(root, i);
		}
	}


	ll root = which[n];
	cout << dp(root, -1);



}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	59996 KB	Output is correct
2	Correct	20 ms	59792 KB	Output is correct
3	Correct	20 ms	59736 KB	Output is correct
4	Correct	21 ms	59728 KB	Output is correct
5	Correct	20 ms	59736 KB	Output is correct
6	Correct	21 ms	59740 KB	Output is correct
7	Correct	21 ms	59736 KB	Output is correct
8	Correct	20 ms	59740 KB	Output is correct
9	Correct	20 ms	59740 KB	Output is correct
10	Correct	23 ms	59736 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	59996 KB	Output is correct
2	Correct	20 ms	59792 KB	Output is correct
3	Correct	20 ms	59736 KB	Output is correct
4	Correct	21 ms	59728 KB	Output is correct
5	Correct	20 ms	59736 KB	Output is correct
6	Correct	21 ms	59740 KB	Output is correct
7	Correct	21 ms	59736 KB	Output is correct
8	Correct	20 ms	59740 KB	Output is correct
9	Correct	20 ms	59740 KB	Output is correct
10	Correct	23 ms	59736 KB	Output is correct
11	Correct	21 ms	59996 KB	Output is correct
12	Correct	20 ms	59996 KB	Output is correct
13	Correct	21 ms	59992 KB	Output is correct
14	Correct	20 ms	59964 KB	Output is correct
15	Correct	20 ms	59996 KB	Output is correct
16	Correct	20 ms	59996 KB	Output is correct
17	Correct	20 ms	59992 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	59996 KB	Output is correct
2	Correct	20 ms	59792 KB	Output is correct
3	Correct	20 ms	59736 KB	Output is correct
4	Correct	21 ms	59728 KB	Output is correct
5	Correct	20 ms	59736 KB	Output is correct
6	Correct	21 ms	59740 KB	Output is correct
7	Correct	21 ms	59736 KB	Output is correct
8	Correct	20 ms	59740 KB	Output is correct
9	Correct	20 ms	59740 KB	Output is correct
10	Correct	23 ms	59736 KB	Output is correct
11	Correct	21 ms	59996 KB	Output is correct
12	Correct	20 ms	59996 KB	Output is correct
13	Correct	21 ms	59992 KB	Output is correct
14	Correct	20 ms	59964 KB	Output is correct
15	Correct	20 ms	59996 KB	Output is correct
16	Correct	20 ms	59996 KB	Output is correct
17	Correct	20 ms	59992 KB	Output is correct
18	Correct	23 ms	60764 KB	Output is correct
19	Correct	23 ms	60760 KB	Output is correct
20	Correct	24 ms	60764 KB	Output is correct
21	Correct	24 ms	60620 KB	Output is correct
22	Correct	26 ms	60652 KB	Output is correct
23	Correct	28 ms	60756 KB	Output is correct
24	Correct	25 ms	60752 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	59996 KB	Output is correct
2	Correct	20 ms	59792 KB	Output is correct
3	Correct	20 ms	59736 KB	Output is correct
4	Correct	21 ms	59728 KB	Output is correct
5	Correct	20 ms	59736 KB	Output is correct
6	Correct	21 ms	59740 KB	Output is correct
7	Correct	21 ms	59736 KB	Output is correct
8	Correct	20 ms	59740 KB	Output is correct
9	Correct	20 ms	59740 KB	Output is correct
10	Correct	23 ms	59736 KB	Output is correct
11	Correct	21 ms	59996 KB	Output is correct
12	Correct	20 ms	59996 KB	Output is correct
13	Correct	21 ms	59992 KB	Output is correct
14	Correct	20 ms	59964 KB	Output is correct
15	Correct	20 ms	59996 KB	Output is correct
16	Correct	20 ms	59996 KB	Output is correct
17	Correct	20 ms	59992 KB	Output is correct
18	Correct	23 ms	60764 KB	Output is correct
19	Correct	23 ms	60760 KB	Output is correct
20	Correct	24 ms	60764 KB	Output is correct
21	Correct	24 ms	60620 KB	Output is correct
22	Correct	26 ms	60652 KB	Output is correct
23	Correct	28 ms	60756 KB	Output is correct
24	Correct	25 ms	60752 KB	Output is correct
25	Correct	20 ms	59740 KB	Output is correct
26	Correct	24 ms	60752 KB	Output is correct
27	Correct	25 ms	60756 KB	Output is correct
28	Correct	24 ms	60764 KB	Output is correct
29	Correct	25 ms	60760 KB	Output is correct
30	Correct	27 ms	60504 KB	Output is correct
31	Correct	28 ms	60500 KB	Output is correct
32	Correct	26 ms	60508 KB	Output is correct
33	Correct	27 ms	60508 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	59996 KB	Output is correct
2	Correct	20 ms	59792 KB	Output is correct
3	Correct	20 ms	59736 KB	Output is correct
4	Correct	21 ms	59728 KB	Output is correct
5	Correct	20 ms	59736 KB	Output is correct
6	Correct	21 ms	59740 KB	Output is correct
7	Correct	21 ms	59736 KB	Output is correct
8	Correct	20 ms	59740 KB	Output is correct
9	Correct	20 ms	59740 KB	Output is correct
10	Correct	23 ms	59736 KB	Output is correct
11	Correct	21 ms	59996 KB	Output is correct
12	Correct	20 ms	59996 KB	Output is correct
13	Correct	21 ms	59992 KB	Output is correct
14	Correct	20 ms	59964 KB	Output is correct
15	Correct	20 ms	59996 KB	Output is correct
16	Correct	20 ms	59996 KB	Output is correct
17	Correct	20 ms	59992 KB	Output is correct
18	Correct	23 ms	60764 KB	Output is correct
19	Correct	23 ms	60760 KB	Output is correct
20	Correct	24 ms	60764 KB	Output is correct
21	Correct	24 ms	60620 KB	Output is correct
22	Correct	26 ms	60652 KB	Output is correct
23	Correct	28 ms	60756 KB	Output is correct
24	Correct	25 ms	60752 KB	Output is correct
25	Correct	195 ms	101200 KB	Output is correct
26	Correct	202 ms	99972 KB	Output is correct
27	Correct	193 ms	100176 KB	Output is correct
28	Correct	376 ms	94800 KB	Output is correct
29	Correct	355 ms	94816 KB	Output is correct
30	Correct	333 ms	95000 KB	Output is correct
31	Correct	337 ms	94916 KB	Output is correct

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	59740 KB	Output is correct
2	Correct	21 ms	59996 KB	Output is correct
3	Correct	250 ms	91472 KB	Output is correct
4	Correct	268 ms	91484 KB	Output is correct
5	Correct	266 ms	91368 KB	Output is correct

Subtask #7
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	59996 KB	Output is correct
2	Correct	20 ms	59792 KB	Output is correct
3	Correct	20 ms	59736 KB	Output is correct
4	Correct	21 ms	59728 KB	Output is correct
5	Correct	20 ms	59736 KB	Output is correct
6	Correct	21 ms	59740 KB	Output is correct
7	Correct	21 ms	59736 KB	Output is correct
8	Correct	20 ms	59740 KB	Output is correct
9	Correct	20 ms	59740 KB	Output is correct
10	Correct	23 ms	59736 KB	Output is correct
11	Correct	21 ms	59996 KB	Output is correct
12	Correct	20 ms	59996 KB	Output is correct
13	Correct	21 ms	59992 KB	Output is correct
14	Correct	20 ms	59964 KB	Output is correct
15	Correct	20 ms	59996 KB	Output is correct
16	Correct	20 ms	59996 KB	Output is correct
17	Correct	20 ms	59992 KB	Output is correct
18	Correct	23 ms	60764 KB	Output is correct
19	Correct	23 ms	60760 KB	Output is correct
20	Correct	24 ms	60764 KB	Output is correct
21	Correct	24 ms	60620 KB	Output is correct
22	Correct	26 ms	60652 KB	Output is correct
23	Correct	28 ms	60756 KB	Output is correct
24	Correct	25 ms	60752 KB	Output is correct
25	Correct	20 ms	59740 KB	Output is correct
26	Correct	24 ms	60752 KB	Output is correct
27	Correct	25 ms	60756 KB	Output is correct
28	Correct	24 ms	60764 KB	Output is correct
29	Correct	25 ms	60760 KB	Output is correct
30	Correct	27 ms	60504 KB	Output is correct
31	Correct	28 ms	60500 KB	Output is correct
32	Correct	26 ms	60508 KB	Output is correct
33	Correct	27 ms	60508 KB	Output is correct
34	Correct	195 ms	101200 KB	Output is correct
35	Correct	202 ms	99972 KB	Output is correct
36	Correct	193 ms	100176 KB	Output is correct
37	Correct	376 ms	94800 KB	Output is correct
38	Correct	355 ms	94816 KB	Output is correct
39	Correct	333 ms	95000 KB	Output is correct
40	Correct	337 ms	94916 KB	Output is correct
41	Correct	22 ms	59740 KB	Output is correct
42	Correct	21 ms	59996 KB	Output is correct
43	Correct	250 ms	91472 KB	Output is correct
44	Correct	268 ms	91484 KB	Output is correct
45	Correct	266 ms	91368 KB	Output is correct
46	Correct	369 ms	97948 KB	Output is correct
47	Correct	358 ms	97876 KB	Output is correct
48	Correct	362 ms	97884 KB	Output is correct
49	Correct	353 ms	97956 KB	Output is correct
50	Correct	328 ms	90144 KB	Output is correct
51	Correct	320 ms	90200 KB	Output is correct
52	Correct	333 ms	89940 KB	Output is correct
53	Correct	321 ms	90196 KB	Output is correct

답안 #1059373

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 7.0 / 7.0

Subtask #3 7.0 / 7.0

Subtask #4 10.0 / 10.0

Subtask #5 20.0 / 20.0

Subtask #6 23.0 / 23.0

Subtask #7 26.0 / 26.0

Subtask #1
7.0 / 7.0

Subtask #2
7.0 / 7.0

Subtask #3
7.0 / 7.0

Subtask #4
10.0 / 10.0

Subtask #5
20.0 / 20.0

Subtask #6
23.0 / 23.0

Subtask #7
26.0 / 26.0