답안 #974586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
974586	2024-05-03T13:32:46 Z	Lecorbio	Cat Exercise (JOI23_ho_t4)	C++14	54 / 100	163 ms	50960 KB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define sajz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 2e5+7, P = 19;
int n, timer = -1, p[N], d[N], tin[N], tout[N], up[N][P]; 
int par[N], sz[N], mx[N], pos[N], dp[N];
vector<int> g[N];

void dfs(int v, int parent){
	tin[v] = ++timer;
	up[v][0] = parent;
	for (int i=1; i<P; i++) up[v][i] = up[up[v][i-1]][i-1];
	for (auto u : g[v]){ 
		if (u == parent) continue;
		d[u] = d[v] + 1;
		dfs(u, v);
	}
	tout[v] = timer;
}

bool ancestor(int a, int b){return tin[a] <= tin[b] && tout[a] >= tout[b];}
int lca(int a, int b){
	if (ancestor(a, b)) return a;
	for (int i=P-1; i>=0; i--){
		if (!ancestor(up[a][i], b)) a = up[a][i];
	}
	return up[a][0];
}

int Find(int a){return a == par[a] ? a : par[a] = Find(par[a]);}
void Union(int a, int b){
	a = Find(a); b = Find(b);
	if (a != b){
		if (sz[a] < sz[b]) swap(a, b);
		sz[a] += sz[b];
		par[b] = a;
		mx[a] = max(mx[a], mx[b]);
	}
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    vector<pair<int,int>> sorted;
    for (int i=1; i<=n; i++){ 
		cin >> p[i];
		sz[i] = 1;
		par[i] = i;
		mx[i] = p[i];
		pos[p[i]] = i;
		sorted.push_back({p[i], i});
	}
	sort(all(sorted));
    for (int i=0; i<n-1; i++){
		int a, b; cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	dfs(1, 1);
	
	int res = 0;
	for (auto [val, v] : sorted){
		//cout << "v: " << v << " --------\n";
		for (auto u : g[v]){
			if (p[u] < val){
				int x = pos[mx[Find(u)]];
				int dist = d[v] + d[x] - 2 * d[lca(v, x)];
				//cout << u << ' ' << x << ": " << lca(v, x) << ' ' << dist << '\n';
				dp[v] = max(dp[v], dp[x] + dist);
				Union(v, u);
			}
		}
		if (val == n) res = v;
	}
	
	//for (int i=1; i<=n; i++) cout << i << ": " << dp[i] << '\n';
	cout << dp[res] << '\n';
 
    return 0;
}
/*

4
3 4 1 2
1 2
2 3
3 4

*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:71:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |  for (auto [val, v] : sorted){
      |            ^

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	12888 KB	Output is correct
2	Correct	2 ms	12892 KB	Output is correct
3	Correct	2 ms	12944 KB	Output is correct
4	Correct	2 ms	12892 KB	Output is correct
5	Correct	2 ms	12892 KB	Output is correct
6	Correct	2 ms	12892 KB	Output is correct
7	Correct	2 ms	12892 KB	Output is correct
8	Correct	3 ms	12892 KB	Output is correct
9	Correct	2 ms	12892 KB	Output is correct
10	Correct	2 ms	12892 KB	Output is correct
11	Correct	2 ms	12892 KB	Output is correct
12	Correct	2 ms	12964 KB	Output is correct
13	Correct	2 ms	12892 KB	Output is correct
14	Correct	2 ms	12892 KB	Output is correct
15	Correct	3 ms	12976 KB	Output is correct
16	Correct	3 ms	12892 KB	Output is correct
17	Correct	2 ms	12932 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	12888 KB	Output is correct
2	Correct	2 ms	12892 KB	Output is correct
3	Correct	2 ms	12944 KB	Output is correct
4	Correct	2 ms	12892 KB	Output is correct
5	Correct	2 ms	12892 KB	Output is correct
6	Correct	2 ms	12892 KB	Output is correct
7	Correct	2 ms	12892 KB	Output is correct
8	Correct	3 ms	12892 KB	Output is correct
9	Correct	2 ms	12892 KB	Output is correct
10	Correct	2 ms	12892 KB	Output is correct
11	Correct	2 ms	12892 KB	Output is correct
12	Correct	2 ms	12964 KB	Output is correct
13	Correct	2 ms	12892 KB	Output is correct
14	Correct	2 ms	12892 KB	Output is correct
15	Correct	3 ms	12976 KB	Output is correct
16	Correct	3 ms	12892 KB	Output is correct
17	Correct	2 ms	12932 KB	Output is correct
18	Correct	4 ms	13652 KB	Output is correct
19	Correct	4 ms	13404 KB	Output is correct
20	Correct	5 ms	13404 KB	Output is correct
21	Correct	5 ms	13400 KB	Output is correct
22	Correct	5 ms	13404 KB	Output is correct
23	Correct	5 ms	13348 KB	Output is correct
24	Correct	5 ms	13460 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	12888 KB	Output is correct
2	Correct	2 ms	12892 KB	Output is correct
3	Correct	2 ms	12944 KB	Output is correct
4	Correct	2 ms	12892 KB	Output is correct
5	Correct	2 ms	12892 KB	Output is correct
6	Correct	2 ms	12892 KB	Output is correct
7	Correct	2 ms	12892 KB	Output is correct
8	Correct	3 ms	12892 KB	Output is correct
9	Correct	2 ms	12892 KB	Output is correct
10	Correct	2 ms	12892 KB	Output is correct
11	Correct	2 ms	12892 KB	Output is correct
12	Correct	2 ms	12964 KB	Output is correct
13	Correct	2 ms	12892 KB	Output is correct
14	Correct	2 ms	12892 KB	Output is correct
15	Correct	3 ms	12976 KB	Output is correct
16	Correct	3 ms	12892 KB	Output is correct
17	Correct	2 ms	12932 KB	Output is correct
18	Correct	4 ms	13652 KB	Output is correct
19	Correct	4 ms	13404 KB	Output is correct
20	Correct	5 ms	13404 KB	Output is correct
21	Correct	5 ms	13400 KB	Output is correct
22	Correct	5 ms	13404 KB	Output is correct
23	Correct	5 ms	13348 KB	Output is correct
24	Correct	5 ms	13460 KB	Output is correct
25	Correct	2 ms	12892 KB	Output is correct
26	Correct	5 ms	13404 KB	Output is correct
27	Correct	5 ms	13404 KB	Output is correct
28	Correct	5 ms	13404 KB	Output is correct
29	Correct	5 ms	13404 KB	Output is correct
30	Correct	5 ms	13148 KB	Output is correct
31	Correct	5 ms	13148 KB	Output is correct
32	Correct	5 ms	13148 KB	Output is correct
33	Correct	6 ms	13204 KB	Output is correct

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	12888 KB	Output is correct
2	Correct	2 ms	12892 KB	Output is correct
3	Correct	2 ms	12944 KB	Output is correct
4	Correct	2 ms	12892 KB	Output is correct
5	Correct	2 ms	12892 KB	Output is correct
6	Correct	2 ms	12892 KB	Output is correct
7	Correct	2 ms	12892 KB	Output is correct
8	Correct	3 ms	12892 KB	Output is correct
9	Correct	2 ms	12892 KB	Output is correct
10	Correct	2 ms	12892 KB	Output is correct
11	Correct	2 ms	12892 KB	Output is correct
12	Correct	2 ms	12964 KB	Output is correct
13	Correct	2 ms	12892 KB	Output is correct
14	Correct	2 ms	12892 KB	Output is correct
15	Correct	3 ms	12976 KB	Output is correct
16	Correct	3 ms	12892 KB	Output is correct
17	Correct	2 ms	12932 KB	Output is correct
18	Correct	4 ms	13652 KB	Output is correct
19	Correct	4 ms	13404 KB	Output is correct
20	Correct	5 ms	13404 KB	Output is correct
21	Correct	5 ms	13400 KB	Output is correct
22	Correct	5 ms	13404 KB	Output is correct
23	Correct	5 ms	13348 KB	Output is correct
24	Correct	5 ms	13460 KB	Output is correct
25	Incorrect	111 ms	50960 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	12888 KB	Output is correct
2	Correct	3 ms	12892 KB	Output is correct
3	Correct	153 ms	38392 KB	Output is correct
4	Correct	163 ms	38340 KB	Output is correct
5	Correct	155 ms	38344 KB	Output is correct

Subtask #7
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	12888 KB	Output is correct
2	Correct	2 ms	12892 KB	Output is correct
3	Correct	2 ms	12944 KB	Output is correct
4	Correct	2 ms	12892 KB	Output is correct
5	Correct	2 ms	12892 KB	Output is correct
6	Correct	2 ms	12892 KB	Output is correct
7	Correct	2 ms	12892 KB	Output is correct
8	Correct	3 ms	12892 KB	Output is correct
9	Correct	2 ms	12892 KB	Output is correct
10	Correct	2 ms	12892 KB	Output is correct
11	Correct	2 ms	12892 KB	Output is correct
12	Correct	2 ms	12964 KB	Output is correct
13	Correct	2 ms	12892 KB	Output is correct
14	Correct	2 ms	12892 KB	Output is correct
15	Correct	3 ms	12976 KB	Output is correct
16	Correct	3 ms	12892 KB	Output is correct
17	Correct	2 ms	12932 KB	Output is correct
18	Correct	4 ms	13652 KB	Output is correct
19	Correct	4 ms	13404 KB	Output is correct
20	Correct	5 ms	13404 KB	Output is correct
21	Correct	5 ms	13400 KB	Output is correct
22	Correct	5 ms	13404 KB	Output is correct
23	Correct	5 ms	13348 KB	Output is correct
24	Correct	5 ms	13460 KB	Output is correct
25	Correct	2 ms	12892 KB	Output is correct
26	Correct	5 ms	13404 KB	Output is correct
27	Correct	5 ms	13404 KB	Output is correct
28	Correct	5 ms	13404 KB	Output is correct
29	Correct	5 ms	13404 KB	Output is correct
30	Correct	5 ms	13148 KB	Output is correct
31	Correct	5 ms	13148 KB	Output is correct
32	Correct	5 ms	13148 KB	Output is correct
33	Correct	6 ms	13204 KB	Output is correct
34	Incorrect	111 ms	50960 KB	Output isn't correct
35	Halted	0 ms	0 KB	-

답안 #974586

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 0 / 20.0

Subtask #6 23.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
10.0 / 10.0

Subtask #5
0 / 20.0

Subtask #6
23.0 / 23.0

Subtask #7
0 / 26.0