답안 #930353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
930353	2024-02-19T12:40:01 Z	koukirocks	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	308 ms	70228 KB

Main

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
 
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;

ll n;
ll p[MAX];
ll pid[MAX];
vector<int> G[MAX];
ll dp[MAX];
ll mx[MAX];
ll sz[MAX];
ll fa[MAX];

void init() {
	for (int i=1;i<=n;i++) {
		fa[i]=i;
		sz[i]=1;
		mx[i]=p[i];
	}
}

int get(int a) {
	return fa[a]=(fa[a]==a?a:get(fa[a]));
}

void unionn(int a,int b) {
	a=get(a);b=get(b);
	if (a==b) return;
	if (sz[a]>sz[b]) swap(a,b);
	fa[a]=b;
	sz[b]+=sz[a];
	mx[b]=max(mx[b],mx[a]);
}

ll up[MAX][20];
ll dep[MAX];

void dfs(int v,int p) {
	up[v][0]=p;
	for (int i=1;i<20;i++) up[v][i]=up[up[v][i-1]][i-1];
	for (int i:G[v]) {
		if (i==p) continue;
		dep[i]=dep[v]+1;
		dfs(i,v);
	}
}

int jump(int v,int k) {
	for (int i=19;i>=0;i--) {
//		cout<<v<<" "<<k<<" "<<i<<"\n";
		if (k&(1<<i)) v=up[v][i];
	}
//	cout<<v<<" fin\n";
	return v;
}

ll dis(int a,int b) {
//	cout<<a<<" "<<b<<" start\n";
//	cout<<dep[a]<<" "<<dep[b]<<" dep\n";
	if (dep[a]<dep[b]) swap(a,b);
	ll ans=dep[a]-dep[b];
	a=jump(a,dep[a]-dep[b]);
//	cout<<a<<" "<<b<<" "<<ans<<"\n";;
	if (a==b) return ans;
	for (int i=19;i>=0;i--) {
		if (up[a][i]!=up[b][i]) {
			a=up[a][i];b=up[b][i];
			ans+=2*(1<<i);
		}
	}
	return ans+2;
}

int main() {
	speed;
	cin>>n;
	for (int i=1;i<=n;i++) {
		cin>>p[i];
		pid[p[i]]=i;
	}
	for (int i=1;i<n;i++) {
		int a,b;
		cin>>a>>b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	init();
	for (int i=0;i<20;i++) up[0][i]=0;
	dep[1]=0;
	dfs(1,0);
	dp[1]=0;
	for (int i=2;i<=n;i++) {
		ll v=pid[i];
		dp[i]=0;
		for (int u:G[v]) {
			if (p[u]<i) {
				dp[i]=max(dp[i],dp[mx[get(u)]]+dis(pid[mx[get(u)]],v));
//				cout<<pid[mx[get(u)]]<<" "<<v<<" "<<dis(pid[mx[get(u)]],v)<<"\n";
				unionn(u,v);
			}
		}
//		for (int i=1;i<=n;i++) cout<<p[i]<<" ";
//		cout<<"\n";
	}
//	for (int i=1;i<=n;i++) cout<<dp[i]<<" ";
//	cout<<"\n";
	cout<<dp[n];
	return 0;
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	16732 KB	Output is correct
2	Correct	3 ms	16732 KB	Output is correct
3	Correct	3 ms	16920 KB	Output is correct
4	Correct	2 ms	16732 KB	Output is correct
5	Correct	2 ms	16732 KB	Output is correct
6	Correct	3 ms	16728 KB	Output is correct
7	Correct	3 ms	16732 KB	Output is correct
8	Correct	2 ms	16732 KB	Output is correct
9	Correct	3 ms	16720 KB	Output is correct
10	Correct	2 ms	16732 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	16732 KB	Output is correct
2	Correct	3 ms	16732 KB	Output is correct
3	Correct	3 ms	16920 KB	Output is correct
4	Correct	2 ms	16732 KB	Output is correct
5	Correct	2 ms	16732 KB	Output is correct
6	Correct	3 ms	16728 KB	Output is correct
7	Correct	3 ms	16732 KB	Output is correct
8	Correct	2 ms	16732 KB	Output is correct
9	Correct	3 ms	16720 KB	Output is correct
10	Correct	2 ms	16732 KB	Output is correct
11	Correct	3 ms	16732 KB	Output is correct
12	Correct	3 ms	16728 KB	Output is correct
13	Correct	4 ms	16732 KB	Output is correct
14	Correct	3 ms	16732 KB	Output is correct
15	Correct	3 ms	16728 KB	Output is correct
16	Correct	3 ms	16724 KB	Output is correct
17	Correct	3 ms	16732 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	16732 KB	Output is correct
2	Correct	3 ms	16732 KB	Output is correct
3	Correct	3 ms	16920 KB	Output is correct
4	Correct	2 ms	16732 KB	Output is correct
5	Correct	2 ms	16732 KB	Output is correct
6	Correct	3 ms	16728 KB	Output is correct
7	Correct	3 ms	16732 KB	Output is correct
8	Correct	2 ms	16732 KB	Output is correct
9	Correct	3 ms	16720 KB	Output is correct
10	Correct	2 ms	16732 KB	Output is correct
11	Correct	3 ms	16732 KB	Output is correct
12	Correct	3 ms	16728 KB	Output is correct
13	Correct	4 ms	16732 KB	Output is correct
14	Correct	3 ms	16732 KB	Output is correct
15	Correct	3 ms	16728 KB	Output is correct
16	Correct	3 ms	16724 KB	Output is correct
17	Correct	3 ms	16732 KB	Output is correct
18	Correct	6 ms	19548 KB	Output is correct
19	Correct	5 ms	19548 KB	Output is correct
20	Correct	6 ms	19544 KB	Output is correct
21	Correct	5 ms	19436 KB	Output is correct
22	Correct	7 ms	19452 KB	Output is correct
23	Correct	5 ms	19548 KB	Output is correct
24	Correct	5 ms	19548 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	16732 KB	Output is correct
2	Correct	3 ms	16732 KB	Output is correct
3	Correct	3 ms	16920 KB	Output is correct
4	Correct	2 ms	16732 KB	Output is correct
5	Correct	2 ms	16732 KB	Output is correct
6	Correct	3 ms	16728 KB	Output is correct
7	Correct	3 ms	16732 KB	Output is correct
8	Correct	2 ms	16732 KB	Output is correct
9	Correct	3 ms	16720 KB	Output is correct
10	Correct	2 ms	16732 KB	Output is correct
11	Correct	3 ms	16732 KB	Output is correct
12	Correct	3 ms	16728 KB	Output is correct
13	Correct	4 ms	16732 KB	Output is correct
14	Correct	3 ms	16732 KB	Output is correct
15	Correct	3 ms	16728 KB	Output is correct
16	Correct	3 ms	16724 KB	Output is correct
17	Correct	3 ms	16732 KB	Output is correct
18	Correct	6 ms	19548 KB	Output is correct
19	Correct	5 ms	19548 KB	Output is correct
20	Correct	6 ms	19544 KB	Output is correct
21	Correct	5 ms	19436 KB	Output is correct
22	Correct	7 ms	19452 KB	Output is correct
23	Correct	5 ms	19548 KB	Output is correct
24	Correct	5 ms	19548 KB	Output is correct
25	Correct	3 ms	16728 KB	Output is correct
26	Correct	6 ms	19416 KB	Output is correct
27	Correct	5 ms	19288 KB	Output is correct
28	Correct	5 ms	19292 KB	Output is correct
29	Correct	5 ms	19292 KB	Output is correct
30	Correct	5 ms	19036 KB	Output is correct
31	Correct	5 ms	19036 KB	Output is correct
32	Correct	5 ms	19036 KB	Output is correct
33	Correct	5 ms	19184 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	16732 KB	Output is correct
2	Correct	3 ms	16732 KB	Output is correct
3	Correct	3 ms	16920 KB	Output is correct
4	Correct	2 ms	16732 KB	Output is correct
5	Correct	2 ms	16732 KB	Output is correct
6	Correct	3 ms	16728 KB	Output is correct
7	Correct	3 ms	16732 KB	Output is correct
8	Correct	2 ms	16732 KB	Output is correct
9	Correct	3 ms	16720 KB	Output is correct
10	Correct	2 ms	16732 KB	Output is correct
11	Correct	3 ms	16732 KB	Output is correct
12	Correct	3 ms	16728 KB	Output is correct
13	Correct	4 ms	16732 KB	Output is correct
14	Correct	3 ms	16732 KB	Output is correct
15	Correct	3 ms	16728 KB	Output is correct
16	Correct	3 ms	16724 KB	Output is correct
17	Correct	3 ms	16732 KB	Output is correct
18	Correct	6 ms	19548 KB	Output is correct
19	Correct	5 ms	19548 KB	Output is correct
20	Correct	6 ms	19544 KB	Output is correct
21	Correct	5 ms	19436 KB	Output is correct
22	Correct	7 ms	19452 KB	Output is correct
23	Correct	5 ms	19548 KB	Output is correct
24	Correct	5 ms	19548 KB	Output is correct
25	Correct	118 ms	69968 KB	Output is correct
26	Correct	113 ms	70032 KB	Output is correct
27	Correct	113 ms	69972 KB	Output is correct
28	Correct	160 ms	70052 KB	Output is correct
29	Correct	156 ms	69968 KB	Output is correct
30	Correct	167 ms	69872 KB	Output is correct
31	Correct	177 ms	70228 KB	Output is correct

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	16868 KB	Output is correct
2	Correct	3 ms	16732 KB	Output is correct
3	Correct	153 ms	57340 KB	Output is correct
4	Correct	153 ms	57172 KB	Output is correct
5	Correct	159 ms	57564 KB	Output is correct

Subtask #7
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	16732 KB	Output is correct
2	Correct	3 ms	16732 KB	Output is correct
3	Correct	3 ms	16920 KB	Output is correct
4	Correct	2 ms	16732 KB	Output is correct
5	Correct	2 ms	16732 KB	Output is correct
6	Correct	3 ms	16728 KB	Output is correct
7	Correct	3 ms	16732 KB	Output is correct
8	Correct	2 ms	16732 KB	Output is correct
9	Correct	3 ms	16720 KB	Output is correct
10	Correct	2 ms	16732 KB	Output is correct
11	Correct	3 ms	16732 KB	Output is correct
12	Correct	3 ms	16728 KB	Output is correct
13	Correct	4 ms	16732 KB	Output is correct
14	Correct	3 ms	16732 KB	Output is correct
15	Correct	3 ms	16728 KB	Output is correct
16	Correct	3 ms	16724 KB	Output is correct
17	Correct	3 ms	16732 KB	Output is correct
18	Correct	6 ms	19548 KB	Output is correct
19	Correct	5 ms	19548 KB	Output is correct
20	Correct	6 ms	19544 KB	Output is correct
21	Correct	5 ms	19436 KB	Output is correct
22	Correct	7 ms	19452 KB	Output is correct
23	Correct	5 ms	19548 KB	Output is correct
24	Correct	5 ms	19548 KB	Output is correct
25	Correct	3 ms	16728 KB	Output is correct
26	Correct	6 ms	19416 KB	Output is correct
27	Correct	5 ms	19288 KB	Output is correct
28	Correct	5 ms	19292 KB	Output is correct
29	Correct	5 ms	19292 KB	Output is correct
30	Correct	5 ms	19036 KB	Output is correct
31	Correct	5 ms	19036 KB	Output is correct
32	Correct	5 ms	19036 KB	Output is correct
33	Correct	5 ms	19184 KB	Output is correct
34	Correct	118 ms	69968 KB	Output is correct
35	Correct	113 ms	70032 KB	Output is correct
36	Correct	113 ms	69972 KB	Output is correct
37	Correct	160 ms	70052 KB	Output is correct
38	Correct	156 ms	69968 KB	Output is correct
39	Correct	167 ms	69872 KB	Output is correct
40	Correct	177 ms	70228 KB	Output is correct
41	Correct	2 ms	16868 KB	Output is correct
42	Correct	3 ms	16732 KB	Output is correct
43	Correct	153 ms	57340 KB	Output is correct
44	Correct	153 ms	57172 KB	Output is correct
45	Correct	159 ms	57564 KB	Output is correct
46	Correct	281 ms	64304 KB	Output is correct
47	Correct	265 ms	63020 KB	Output is correct
48	Correct	308 ms	64912 KB	Output is correct
49	Correct	267 ms	63272 KB	Output is correct
50	Correct	226 ms	57352 KB	Output is correct
51	Correct	228 ms	57424 KB	Output is correct
52	Correct	221 ms	57384 KB	Output is correct
53	Correct	239 ms	57728 KB	Output is correct

답안 #930353

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