답안 #802966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802966	2023-08-02T16:45:59 Z	aymanrs	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	345 ms	69648 KB

Main

#include<bits/stdc++.h>
using namespace std;
const int L = 18;
struct node {
	vector<node*> l; // neighbors in the original graph
	vector<node*> c; // children in the CT
	int a, id; // a is the value of the node, id is its index
	bool v = false; // initially, no node is marked
	node* anc[L];
};
// <DSU>
int f(int i, int r[]){ // find representant of i
	if(r[i] == i) return i;
	return r[i] = f(r[i], r);
}
void merge(int a, int b, int r[], int s[]){
	a = f(a, r);
	b = f(b, r);
	if(a == b) return;
	if(s[a] > s[b]){
		r[b] = a;
		s[a] += s[b];
	} else {
		r[a] = b;
		s[b] += s[a];
	}
}
// </DSU>
int dist(node* u, node* v){
	if(u->a < v->a) swap(u, v);
	int d = u->a-v->a;
	for(int i = 0;i < L;i++) if(d&(1<<i)) u = u->anc[i];
	if(u == v) return d;
	for(int i = L-1;i >= 0;i--){
		if(u->anc[i] != v->anc[i]){
			u = u->anc[i];
			v = v->anc[i];
			d += 2<<i;
		}
	}
	return d+2;
}
long long dfs(node* n){
	long long r = 0;
	for(node* c : n->c) r = max(r, dfs(c)+dist(n, c));
	return r;
}
void se(node* n, node* p, int d){
	n->anc[0] = p;
	n->a = d;
	for(int i = 1;i < L;i++) n->anc[i] = n->anc[i-1]->anc[i-1]; 
	for(node* c : n->l) if(c!=p) se(c, n, d+1);
}
void solve(){
	// <boring setup>
	int n,u,v;
	cin >> n;
	int m = n-1;
	node g[n+1];
	int o[n], r[n+1], s[n+1];
	node* c[n+1]; // c[u] is the node with maximum value that u is connected to in the DSU, if u is its own representant
	for(int i = 1;i <= n;i++) {
		cin >> g[i].a;
		g[i].id = i;
		r[i] = i;
		s[i] = 1;
		c[i] = &g[i];
		o[i-1] = i;
	}
	while(m--){
		cin >> u >> v;
		g[u].l.push_back(&g[v]);
		g[v].l.push_back(&g[u]);
	}
	// </boring setup>
	sort(o, o+n, [&g](int a, int b){return g[a].a < g[b].a;}); // sorting the nodes by value
	for(int j = 0;j < n;j++){
		node* d = &g[o[j]]; // d is the current node
		d->v = true; // mark the current node
		for(node* x : d->l){ // iterate over the neighbors of d
			if(!x->v || f(x->id, r) == f(d->id, r)) continue; // x is unmarked or it's already connected to d
			d->c.push_back(c[f(x->id, r)]); // add and edge in the CT between d and the node with maximum value that is connected to x
			merge(x->id, d->id, r, s); // connect d and x in the DSU
			c[f(d->id, r)] = d;
		}
	}
	// Use the CT
	se(&g[1], &g[1], 0);
	cout << dfs(&g[o[n-1]]) << '\n';
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	316 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	320 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	3 ms	2004 KB	Output is correct
19	Correct	3 ms	1996 KB	Output is correct
20	Correct	3 ms	2016 KB	Output is correct
21	Correct	3 ms	1876 KB	Output is correct
22	Correct	4 ms	1856 KB	Output is correct
23	Correct	3 ms	2004 KB	Output is correct
24	Correct	3 ms	1876 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	316 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	320 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	3 ms	2004 KB	Output is correct
19	Correct	3 ms	1996 KB	Output is correct
20	Correct	3 ms	2016 KB	Output is correct
21	Correct	3 ms	1876 KB	Output is correct
22	Correct	4 ms	1856 KB	Output is correct
23	Correct	3 ms	2004 KB	Output is correct
24	Correct	3 ms	1876 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	4 ms	1924 KB	Output is correct
27	Correct	4 ms	1868 KB	Output is correct
28	Correct	4 ms	2004 KB	Output is correct
29	Correct	3 ms	1876 KB	Output is correct
30	Correct	4 ms	1748 KB	Output is correct
31	Correct	3 ms	1748 KB	Output is correct
32	Correct	3 ms	1744 KB	Output is correct
33	Correct	3 ms	1748 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	316 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	320 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	3 ms	2004 KB	Output is correct
19	Correct	3 ms	1996 KB	Output is correct
20	Correct	3 ms	2016 KB	Output is correct
21	Correct	3 ms	1876 KB	Output is correct
22	Correct	4 ms	1856 KB	Output is correct
23	Correct	3 ms	2004 KB	Output is correct
24	Correct	3 ms	1876 KB	Output is correct
25	Correct	177 ms	69648 KB	Output is correct
26	Correct	166 ms	69072 KB	Output is correct
27	Correct	156 ms	68976 KB	Output is correct
28	Correct	223 ms	67476 KB	Output is correct
29	Correct	207 ms	67564 KB	Output is correct
30	Correct	204 ms	67452 KB	Output is correct
31	Correct	200 ms	67476 KB	Output is correct

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	238 ms	60576 KB	Output is correct
4	Correct	231 ms	60660 KB	Output is correct
5	Correct	231 ms	60540 KB	Output is correct

Subtask #7
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	316 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	320 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	3 ms	2004 KB	Output is correct
19	Correct	3 ms	1996 KB	Output is correct
20	Correct	3 ms	2016 KB	Output is correct
21	Correct	3 ms	1876 KB	Output is correct
22	Correct	4 ms	1856 KB	Output is correct
23	Correct	3 ms	2004 KB	Output is correct
24	Correct	3 ms	1876 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	4 ms	1924 KB	Output is correct
27	Correct	4 ms	1868 KB	Output is correct
28	Correct	4 ms	2004 KB	Output is correct
29	Correct	3 ms	1876 KB	Output is correct
30	Correct	4 ms	1748 KB	Output is correct
31	Correct	3 ms	1748 KB	Output is correct
32	Correct	3 ms	1744 KB	Output is correct
33	Correct	3 ms	1748 KB	Output is correct
34	Correct	177 ms	69648 KB	Output is correct
35	Correct	166 ms	69072 KB	Output is correct
36	Correct	156 ms	68976 KB	Output is correct
37	Correct	223 ms	67476 KB	Output is correct
38	Correct	207 ms	67564 KB	Output is correct
39	Correct	204 ms	67452 KB	Output is correct
40	Correct	200 ms	67476 KB	Output is correct
41	Correct	0 ms	212 KB	Output is correct
42	Correct	1 ms	340 KB	Output is correct
43	Correct	238 ms	60576 KB	Output is correct
44	Correct	231 ms	60660 KB	Output is correct
45	Correct	231 ms	60540 KB	Output is correct
46	Correct	333 ms	66412 KB	Output is correct
47	Correct	326 ms	66428 KB	Output is correct
48	Correct	320 ms	66380 KB	Output is correct
49	Correct	345 ms	66436 KB	Output is correct
50	Correct	341 ms	59384 KB	Output is correct
51	Correct	313 ms	59384 KB	Output is correct
52	Correct	329 ms	59360 KB	Output is correct
53	Correct	320 ms	59404 KB	Output is correct

답안 #802966

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