답안 #861475

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
861475	2023-10-16T09:46:30 Z	NotLinux	Cat Exercise (JOI23_ho_t4)	C++17	21 / 100	111 ms	40708 KB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
const int M = 20;
int n,p[N],lift[N][M],depth[N];
vector < int > tree[N];
pair < int , int > ord[N];
inline void dfs(int node , int par , int dpt){
	lift[node][0] = par;
	depth[node] = dpt;
	for(int i = 0;i<(int)tree[node].size();i++){
		if(par != tree[node][i]){
			dfs(tree[node][i],node,dpt+1);
		}
	}
}
inline int lca(int a , int b){
	if(depth[a] > depth[b])swap(a,b);
	int diff = depth[b] - depth[a];
	for(int i = 0;i<M;i++){
		if((diff >> i) & 1){
			b = lift[b][i];
		}
	}
	if(a == b)return a;
	for(int i = 0;i<M;i++){
		if(lift[a][i] != lift[b][i]){
			a = lift[a][i];
			b = lift[b][i];
		}
	}
	return lift[a][0];
}
inline int dist(int a , int b){
	return depth[a] + depth[b] - 2 * depth[lca(a,b)];
}
struct DSU{
	vector < int > par,dp;
	DSU(int x){
		x += 3;
		par.resize(x);
		iota(par.begin() , par.end() , 0);
		dp.assign(x,0);
	}
	int find(int a){
		if(par[a] == a)return a;
		return par[a] = find(par[a]);
	}
	void merge(int a , int b){//a -> b
		a = find(a) , b = find(b);
		dp[b] = max(dp[b] , dp[a] + dist(a,b) );
		par[a] = b;
	}
} dsu(N);
void solve(){
	cin >> n;
	for(int i = 0;i<n;i++){
		cin >> p[i];
		ord[i] = {p[i],i};
	}
	sort(ord , ord + n);
	for(int i = 1;i<n;i++){
		int ai,bi;cin >> ai >> bi;
		ai--;bi--;
		tree[ai].push_back(bi);
		tree[bi].push_back(ai);
	}
	//calculating lca
	dfs(0,0,0);
	for(int i = 1;i<M;i++){
		for(int j = 0;j<n;j++){
			lift[j][i] = lift[lift[j][i-1]][i-1];
		}
	}
	int ans = 0;
	for(int i = 0;i<n;i++){
		for(auto itr : tree[ord[i].second]){
			if(p[itr] < ord[i].first){
				dsu.merge(itr , ord[i].second);
			}
		}
		ans = max(ans , dsu.dp[ord[i].second]);
	}
	cout << ans << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	12124 KB	Output is correct
2	Correct	3 ms	12124 KB	Output is correct
3	Correct	3 ms	12124 KB	Output is correct
4	Correct	2 ms	12304 KB	Output is correct
5	Correct	2 ms	12124 KB	Output is correct
6	Correct	2 ms	12124 KB	Output is correct
7	Correct	2 ms	12124 KB	Output is correct
8	Correct	3 ms	12124 KB	Output is correct
9	Correct	2 ms	12124 KB	Output is correct
10	Correct	2 ms	12124 KB	Output is correct
11	Correct	2 ms	12124 KB	Output is correct
12	Correct	3 ms	12124 KB	Output is correct
13	Correct	3 ms	12120 KB	Output is correct
14	Correct	3 ms	12120 KB	Output is correct
15	Correct	2 ms	12124 KB	Output is correct
16	Correct	3 ms	12124 KB	Output is correct
17	Correct	3 ms	12304 KB	Output is correct
18	Correct	6 ms	12636 KB	Output is correct
19	Correct	5 ms	12576 KB	Output is correct
20	Correct	4 ms	12636 KB	Output is correct
21	Correct	5 ms	12636 KB	Output is correct
22	Correct	4 ms	12636 KB	Output is correct
23	Correct	4 ms	12636 KB	Output is correct
24	Correct	4 ms	12636 KB	Output is correct

Subtask #4
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	12124 KB	Output is correct
2	Correct	3 ms	12124 KB	Output is correct
3	Correct	3 ms	12124 KB	Output is correct
4	Correct	2 ms	12304 KB	Output is correct
5	Correct	2 ms	12124 KB	Output is correct
6	Correct	2 ms	12124 KB	Output is correct
7	Correct	2 ms	12124 KB	Output is correct
8	Correct	3 ms	12124 KB	Output is correct
9	Correct	2 ms	12124 KB	Output is correct
10	Correct	2 ms	12124 KB	Output is correct
11	Correct	2 ms	12124 KB	Output is correct
12	Correct	3 ms	12124 KB	Output is correct
13	Correct	3 ms	12120 KB	Output is correct
14	Correct	3 ms	12120 KB	Output is correct
15	Correct	2 ms	12124 KB	Output is correct
16	Correct	3 ms	12124 KB	Output is correct
17	Correct	3 ms	12304 KB	Output is correct
18	Correct	6 ms	12636 KB	Output is correct
19	Correct	5 ms	12576 KB	Output is correct
20	Correct	4 ms	12636 KB	Output is correct
21	Correct	5 ms	12636 KB	Output is correct
22	Correct	4 ms	12636 KB	Output is correct
23	Correct	4 ms	12636 KB	Output is correct
24	Correct	4 ms	12636 KB	Output is correct
25	Correct	3 ms	12120 KB	Output is correct
26	Incorrect	5 ms	12636 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	12124 KB	Output is correct
2	Correct	3 ms	12124 KB	Output is correct
3	Correct	3 ms	12124 KB	Output is correct
4	Correct	2 ms	12304 KB	Output is correct
5	Correct	2 ms	12124 KB	Output is correct
6	Correct	2 ms	12124 KB	Output is correct
7	Correct	2 ms	12124 KB	Output is correct
8	Correct	3 ms	12124 KB	Output is correct
9	Correct	2 ms	12124 KB	Output is correct
10	Correct	2 ms	12124 KB	Output is correct
11	Correct	2 ms	12124 KB	Output is correct
12	Correct	3 ms	12124 KB	Output is correct
13	Correct	3 ms	12120 KB	Output is correct
14	Correct	3 ms	12120 KB	Output is correct
15	Correct	2 ms	12124 KB	Output is correct
16	Correct	3 ms	12124 KB	Output is correct
17	Correct	3 ms	12304 KB	Output is correct
18	Correct	6 ms	12636 KB	Output is correct
19	Correct	5 ms	12576 KB	Output is correct
20	Correct	4 ms	12636 KB	Output is correct
21	Correct	5 ms	12636 KB	Output is correct
22	Correct	4 ms	12636 KB	Output is correct
23	Correct	4 ms	12636 KB	Output is correct
24	Correct	4 ms	12636 KB	Output is correct
25	Incorrect	111 ms	40708 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #6
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	12124 KB	Output is correct
2	Incorrect	2 ms	12124 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #7
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	12124 KB	Output is correct
2	Correct	3 ms	12124 KB	Output is correct
3	Correct	3 ms	12124 KB	Output is correct
4	Correct	2 ms	12304 KB	Output is correct
5	Correct	2 ms	12124 KB	Output is correct
6	Correct	2 ms	12124 KB	Output is correct
7	Correct	2 ms	12124 KB	Output is correct
8	Correct	3 ms	12124 KB	Output is correct
9	Correct	2 ms	12124 KB	Output is correct
10	Correct	2 ms	12124 KB	Output is correct
11	Correct	2 ms	12124 KB	Output is correct
12	Correct	3 ms	12124 KB	Output is correct
13	Correct	3 ms	12120 KB	Output is correct
14	Correct	3 ms	12120 KB	Output is correct
15	Correct	2 ms	12124 KB	Output is correct
16	Correct	3 ms	12124 KB	Output is correct
17	Correct	3 ms	12304 KB	Output is correct
18	Correct	6 ms	12636 KB	Output is correct
19	Correct	5 ms	12576 KB	Output is correct
20	Correct	4 ms	12636 KB	Output is correct
21	Correct	5 ms	12636 KB	Output is correct
22	Correct	4 ms	12636 KB	Output is correct
23	Correct	4 ms	12636 KB	Output is correct
24	Correct	4 ms	12636 KB	Output is correct
25	Correct	3 ms	12120 KB	Output is correct
26	Incorrect	5 ms	12636 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

답안 #861475

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 7.0 / 7.0

Subtask #3 7.0 / 7.0

Subtask #4 0 / 10.0

Subtask #5 0 / 20.0

Subtask #6 0 / 23.0

Subtask #7 0 / 26.0

Subtask #1
7.0 / 7.0

Subtask #2
7.0 / 7.0

Subtask #3
7.0 / 7.0

Subtask #4
0 / 10.0

Subtask #5
0 / 20.0

Subtask #6
0 / 23.0

Subtask #7
0 / 26.0