답안 #878472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
878472	2023-11-24T13:17:58 Z	phoenix0423	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	222 ms	51960 KB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define f first
#define s second
const int INF = 1e9;
const int maxn = 2e5 + 5;
vector<int> adj[maxn];
int h[maxn], id[maxn], n;
vector<pll> edge;
int dep[maxn], par[maxn], succ[maxn][18];
struct DSU{
	vector<int> par, siz;
	int n;
	DSU(int _n) : n(_n){
		par.resize(n);
		for(int i = 0; i < n; i++) par[i] = i;
	}
	int root(int x){ return x == par[x] ? x : par[x] = root(par[x]);}
	void unite(int x, int y){
		y = root(y); // h[x] > h[y]
		par[y] = x;
	}
};

void dfs(int pos, int prev){
	for(int i = 1; i < 18; i++) succ[pos][i] = succ[succ[pos][i - 1]][i - 1];
	for(auto x : adj[pos]){
		if(x == prev) continue;
		dep[x] = dep[pos] + 1;
		succ[x][0] = pos;
		dfs(x, pos);
	}
}
void lift(int &b, int steps){
	for(int i = 17; i >= 0; i--){
		if(steps & (1 << i)) b = succ[b][i];
	}
}
int sld(int a, int b){
	int ret = 0;
	for(int i = 17; i >= 0; i--){
		if(succ[a][i] != succ[b][i]){
			a = succ[a][i];
			b = succ[b][i];
			ret += (1 << i) * 2;
		}
	}
	return ret + 2;
}
int dist(int a, int b){
	int ret = 0;
	if(dep[a] > dep[b]) swap(a, b);
	ret += dep[b] - dep[a], lift(b, dep[b] - dep[a]);
	if(a == b) return ret;
	return ret + sld(a, b);
}
int main(void){
	fastio;
	cin>>n;
	for(int i = 0; i < n; i++) cin>>h[i], h[i]--, id[h[i]] = i;
	for(int i = 0; i < n - 1; i++){
		int a, b;
		cin>>a>>b;
		a--, b--;
		adj[a].pb(b);
		adj[b].pb(a);
		if(h[a] < h[b]) swap(a, b);
		edge.eb(a, b);
	}
	sort(ALL(edge), [&](pll a, pll b) -> bool { return h[a.f] < h[b.f];});
	dfs(0, 0);
	DSU dsu(n);
	vector<ll> ans(n); // store ans of element of height i
	for(auto [a, b] : edge){ // h[a] > h[b]
		b = dsu.root(b);
		ans[h[a]] = max(ans[h[a]], ans[h[b]] + dist(a, b));
		dsu.unite(a, b);
	}
	cout<<ans[n - 1]<<"\n";
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	7772 KB	Output is correct
2	Correct	2 ms	7844 KB	Output is correct
3	Correct	2 ms	7768 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7772 KB	Output is correct
6	Correct	2 ms	7836 KB	Output is correct
7	Correct	2 ms	7840 KB	Output is correct
8	Correct	2 ms	7772 KB	Output is correct
9	Correct	2 ms	7772 KB	Output is correct
10	Correct	2 ms	7780 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	7772 KB	Output is correct
2	Correct	2 ms	7844 KB	Output is correct
3	Correct	2 ms	7768 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7772 KB	Output is correct
6	Correct	2 ms	7836 KB	Output is correct
7	Correct	2 ms	7840 KB	Output is correct
8	Correct	2 ms	7772 KB	Output is correct
9	Correct	2 ms	7772 KB	Output is correct
10	Correct	2 ms	7780 KB	Output is correct
11	Correct	2 ms	7772 KB	Output is correct
12	Correct	2 ms	7772 KB	Output is correct
13	Correct	2 ms	7772 KB	Output is correct
14	Correct	2 ms	7772 KB	Output is correct
15	Correct	2 ms	7772 KB	Output is correct
16	Correct	2 ms	7772 KB	Output is correct
17	Correct	2 ms	7768 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	7772 KB	Output is correct
2	Correct	2 ms	7844 KB	Output is correct
3	Correct	2 ms	7768 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7772 KB	Output is correct
6	Correct	2 ms	7836 KB	Output is correct
7	Correct	2 ms	7840 KB	Output is correct
8	Correct	2 ms	7772 KB	Output is correct
9	Correct	2 ms	7772 KB	Output is correct
10	Correct	2 ms	7780 KB	Output is correct
11	Correct	2 ms	7772 KB	Output is correct
12	Correct	2 ms	7772 KB	Output is correct
13	Correct	2 ms	7772 KB	Output is correct
14	Correct	2 ms	7772 KB	Output is correct
15	Correct	2 ms	7772 KB	Output is correct
16	Correct	2 ms	7772 KB	Output is correct
17	Correct	2 ms	7768 KB	Output is correct
18	Correct	4 ms	10588 KB	Output is correct
19	Correct	4 ms	10668 KB	Output is correct
20	Correct	4 ms	10636 KB	Output is correct
21	Correct	4 ms	10840 KB	Output is correct
22	Correct	4 ms	10588 KB	Output is correct
23	Correct	6 ms	10588 KB	Output is correct
24	Correct	4 ms	10588 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	7772 KB	Output is correct
2	Correct	2 ms	7844 KB	Output is correct
3	Correct	2 ms	7768 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7772 KB	Output is correct
6	Correct	2 ms	7836 KB	Output is correct
7	Correct	2 ms	7840 KB	Output is correct
8	Correct	2 ms	7772 KB	Output is correct
9	Correct	2 ms	7772 KB	Output is correct
10	Correct	2 ms	7780 KB	Output is correct
11	Correct	2 ms	7772 KB	Output is correct
12	Correct	2 ms	7772 KB	Output is correct
13	Correct	2 ms	7772 KB	Output is correct
14	Correct	2 ms	7772 KB	Output is correct
15	Correct	2 ms	7772 KB	Output is correct
16	Correct	2 ms	7772 KB	Output is correct
17	Correct	2 ms	7768 KB	Output is correct
18	Correct	4 ms	10588 KB	Output is correct
19	Correct	4 ms	10668 KB	Output is correct
20	Correct	4 ms	10636 KB	Output is correct
21	Correct	4 ms	10840 KB	Output is correct
22	Correct	4 ms	10588 KB	Output is correct
23	Correct	6 ms	10588 KB	Output is correct
24	Correct	4 ms	10588 KB	Output is correct
25	Correct	2 ms	7768 KB	Output is correct
26	Correct	5 ms	10588 KB	Output is correct
27	Correct	4 ms	10588 KB	Output is correct
28	Correct	5 ms	10584 KB	Output is correct
29	Correct	5 ms	10576 KB	Output is correct
30	Correct	4 ms	10332 KB	Output is correct
31	Correct	5 ms	10332 KB	Output is correct
32	Correct	4 ms	10332 KB	Output is correct
33	Correct	5 ms	10332 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	7772 KB	Output is correct
2	Correct	2 ms	7844 KB	Output is correct
3	Correct	2 ms	7768 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7772 KB	Output is correct
6	Correct	2 ms	7836 KB	Output is correct
7	Correct	2 ms	7840 KB	Output is correct
8	Correct	2 ms	7772 KB	Output is correct
9	Correct	2 ms	7772 KB	Output is correct
10	Correct	2 ms	7780 KB	Output is correct
11	Correct	2 ms	7772 KB	Output is correct
12	Correct	2 ms	7772 KB	Output is correct
13	Correct	2 ms	7772 KB	Output is correct
14	Correct	2 ms	7772 KB	Output is correct
15	Correct	2 ms	7772 KB	Output is correct
16	Correct	2 ms	7772 KB	Output is correct
17	Correct	2 ms	7768 KB	Output is correct
18	Correct	4 ms	10588 KB	Output is correct
19	Correct	4 ms	10668 KB	Output is correct
20	Correct	4 ms	10636 KB	Output is correct
21	Correct	4 ms	10840 KB	Output is correct
22	Correct	4 ms	10588 KB	Output is correct
23	Correct	6 ms	10588 KB	Output is correct
24	Correct	4 ms	10588 KB	Output is correct
25	Correct	105 ms	51788 KB	Output is correct
26	Correct	101 ms	51960 KB	Output is correct
27	Correct	107 ms	51912 KB	Output is correct
28	Correct	113 ms	51812 KB	Output is correct
29	Correct	110 ms	51760 KB	Output is correct
30	Correct	115 ms	51768 KB	Output is correct
31	Correct	128 ms	51832 KB	Output is correct

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	7840 KB	Output is correct
2	Correct	2 ms	7772 KB	Output is correct
3	Correct	122 ms	36208 KB	Output is correct
4	Correct	110 ms	36028 KB	Output is correct
5	Correct	131 ms	36028 KB	Output is correct

Subtask #7
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	7772 KB	Output is correct
2	Correct	2 ms	7844 KB	Output is correct
3	Correct	2 ms	7768 KB	Output is correct
4	Correct	2 ms	7772 KB	Output is correct
5	Correct	2 ms	7772 KB	Output is correct
6	Correct	2 ms	7836 KB	Output is correct
7	Correct	2 ms	7840 KB	Output is correct
8	Correct	2 ms	7772 KB	Output is correct
9	Correct	2 ms	7772 KB	Output is correct
10	Correct	2 ms	7780 KB	Output is correct
11	Correct	2 ms	7772 KB	Output is correct
12	Correct	2 ms	7772 KB	Output is correct
13	Correct	2 ms	7772 KB	Output is correct
14	Correct	2 ms	7772 KB	Output is correct
15	Correct	2 ms	7772 KB	Output is correct
16	Correct	2 ms	7772 KB	Output is correct
17	Correct	2 ms	7768 KB	Output is correct
18	Correct	4 ms	10588 KB	Output is correct
19	Correct	4 ms	10668 KB	Output is correct
20	Correct	4 ms	10636 KB	Output is correct
21	Correct	4 ms	10840 KB	Output is correct
22	Correct	4 ms	10588 KB	Output is correct
23	Correct	6 ms	10588 KB	Output is correct
24	Correct	4 ms	10588 KB	Output is correct
25	Correct	2 ms	7768 KB	Output is correct
26	Correct	5 ms	10588 KB	Output is correct
27	Correct	4 ms	10588 KB	Output is correct
28	Correct	5 ms	10584 KB	Output is correct
29	Correct	5 ms	10576 KB	Output is correct
30	Correct	4 ms	10332 KB	Output is correct
31	Correct	5 ms	10332 KB	Output is correct
32	Correct	4 ms	10332 KB	Output is correct
33	Correct	5 ms	10332 KB	Output is correct
34	Correct	105 ms	51788 KB	Output is correct
35	Correct	101 ms	51960 KB	Output is correct
36	Correct	107 ms	51912 KB	Output is correct
37	Correct	113 ms	51812 KB	Output is correct
38	Correct	110 ms	51760 KB	Output is correct
39	Correct	115 ms	51768 KB	Output is correct
40	Correct	128 ms	51832 KB	Output is correct
41	Correct	2 ms	7840 KB	Output is correct
42	Correct	2 ms	7772 KB	Output is correct
43	Correct	122 ms	36208 KB	Output is correct
44	Correct	110 ms	36028 KB	Output is correct
45	Correct	131 ms	36028 KB	Output is correct
46	Correct	173 ms	44808 KB	Output is correct
47	Correct	182 ms	43508 KB	Output is correct
48	Correct	176 ms	45500 KB	Output is correct
49	Correct	171 ms	43456 KB	Output is correct
50	Correct	222 ms	36396 KB	Output is correct
51	Correct	169 ms	36288 KB	Output is correct
52	Correct	177 ms	36216 KB	Output is correct
53	Correct	176 ms	36288 KB	Output is correct

답안 #878472

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