oj.uz

Submission #974586

# Submission time Handle Problem Language Result Execution time Memory
974586 2024-05-03T13:32:46 Z Lecorbio Cat Exercise (JOI23_ho_t4) C++14
54 / 100
 163 ms 50960 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -