oj.uz

Submission #1102498

# Submission time Handle Problem Language Result Execution time Memory
1102498 2024-10-18T08:05:37 Z hqminhuwu Cat Exercise (JOI23_ho_t4) C++14
100 / 100
 175 ms 81316 KB 
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

template<class X, class Y>
	bool minz(X &x, const Y &y) {
		if (x > y) {
			x = y;
			return true;
		} return false;
	}
template<class X, class Y>
	bool maxz(X &x, const Y &y) {
		if (x < y) {
			x = y;
			return true;
		} return false;
	}

const int N = 5e5 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;

int dep[N], up[20][N], par[N], sz[N], mx[N], a[N], u, v, n;
ll dp[N];
vector <int> g[N];

void dfs(int u){
	for (int v : g[u]){
		if (dep[v]) continue;
		dep[v] = dep[u] + 1;
		up[0][v] = u;
		forr (i, 1, 17)
			up[i][v] = up[i - 1][up[i - 1][v]]; 
		dfs(v);
	}
}

int lca (int u, int v){
	if (dep[u] < dep[v]) swap(u, v);
	
	int k = dep[u] - dep[v];
	ford (i, 17, 0)
	if (bit(k, i))
		u = up[i][u];

	if (u == v){
		return u;
	}

	ford (i, 17, 0)
	if (up[i][u] != up[i][v]){
		u = up[i][u];
		v = up[i][v];
	}

	return up[0][u];
}

int get (int u){
	return u == par[u] ? u : par[u] = get(par[u]);
}

bool update (int u, int v){
	u = get(u); v = get(v);
	if (u == v) return 0;
	
	if (sz[u] < sz[v]) swap(u, v);
	par[v] = u;
	sz[u] += sz[v];
	maxz(mx[u], mx[v]);
	return 1;
}

int dis (int u, int v){
	return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	#ifdef kaguya
		freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
	#endif

	cin >> n;

	forr (i, 1, n){
		cin >> a[i];
		sz[i] = 1;
		par[i] = i;
		mx[i] = i; 
	}

	forf (i, 1, n){
		cin >> u >> v;
		g[a[u]].pb(a[v]);
		g[a[v]].pb(a[u]);
	}

	dep[1] = 1;
	dfs(1);	

	forr (i, 1, n){
		for (int v : g[i])
		if (v < i){
			int k = mx[get(v)];
			maxz(dp[i], dp[k] + dis(i, k));
			update(i, v);
		}
	}

	cout << dp[n] << "\n";

	return 0;
}
/*



*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 58108 KB Output is correct
2 Correct 7 ms 57940 KB Output is correct
3 Correct 7 ms 57940 KB Output is correct
4 Correct 7 ms 57940 KB Output is correct
5 Correct 10 ms 57940 KB Output is correct
6 Correct 7 ms 58108 KB Output is correct
7 Correct 9 ms 57940 KB Output is correct
8 Correct 8 ms 58064 KB Output is correct
9 Correct 8 ms 57940 KB Output is correct
10 Correct 8 ms 57940 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 58108 KB Output is correct
2 Correct 7 ms 57940 KB Output is correct
3 Correct 7 ms 57940 KB Output is correct
4 Correct 7 ms 57940 KB Output is correct
5 Correct 10 ms 57940 KB Output is correct
6 Correct 7 ms 58108 KB Output is correct
7 Correct 9 ms 57940 KB Output is correct
8 Correct 8 ms 58064 KB Output is correct
9 Correct 8 ms 57940 KB Output is correct
10 Correct 8 ms 57940 KB Output is correct
11 Correct 7 ms 57940 KB Output is correct
12 Correct 7 ms 57940 KB Output is correct
13 Correct 8 ms 58116 KB Output is correct
14 Correct 7 ms 57940 KB Output is correct
15 Correct 8 ms 58016 KB Output is correct
16 Correct 7 ms 57940 KB Output is correct
17 Correct 8 ms 57952 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 58108 KB Output is correct
2 Correct 7 ms 57940 KB Output is correct
3 Correct 7 ms 57940 KB Output is correct
4 Correct 7 ms 57940 KB Output is correct
5 Correct 10 ms 57940 KB Output is correct
6 Correct 7 ms 58108 KB Output is correct
7 Correct 9 ms 57940 KB Output is correct
8 Correct 8 ms 58064 KB Output is correct
9 Correct 8 ms 57940 KB Output is correct
10 Correct 8 ms 57940 KB Output is correct
11 Correct 7 ms 57940 KB Output is correct
12 Correct 7 ms 57940 KB Output is correct
13 Correct 8 ms 58116 KB Output is correct
14 Correct 7 ms 57940 KB Output is correct
15 Correct 8 ms 58016 KB Output is correct
16 Correct 7 ms 57940 KB Output is correct
17 Correct 8 ms 57952 KB Output is correct
18 Correct 9 ms 58308 KB Output is correct
19 Correct 10 ms 58616 KB Output is correct
20 Correct 9 ms 58452 KB Output is correct
21 Correct 10 ms 58288 KB Output is correct
22 Correct 9 ms 58452 KB Output is correct
23 Correct 10 ms 58484 KB Output is correct
24 Correct 10 ms 58452 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 58108 KB Output is correct
2 Correct 7 ms 57940 KB Output is correct
3 Correct 7 ms 57940 KB Output is correct
4 Correct 7 ms 57940 KB Output is correct
5 Correct 10 ms 57940 KB Output is correct
6 Correct 7 ms 58108 KB Output is correct
7 Correct 9 ms 57940 KB Output is correct
8 Correct 8 ms 58064 KB Output is correct
9 Correct 8 ms 57940 KB Output is correct
10 Correct 8 ms 57940 KB Output is correct
11 Correct 7 ms 57940 KB Output is correct
12 Correct 7 ms 57940 KB Output is correct
13 Correct 8 ms 58116 KB Output is correct
14 Correct 7 ms 57940 KB Output is correct
15 Correct 8 ms 58016 KB Output is correct
16 Correct 7 ms 57940 KB Output is correct
17 Correct 8 ms 57952 KB Output is correct
18 Correct 9 ms 58308 KB Output is correct
19 Correct 10 ms 58616 KB Output is correct
20 Correct 9 ms 58452 KB Output is correct
21 Correct 10 ms 58288 KB Output is correct
22 Correct 9 ms 58452 KB Output is correct
23 Correct 10 ms 58484 KB Output is correct
24 Correct 10 ms 58452 KB Output is correct
25 Correct 8 ms 58020 KB Output is correct
26 Correct 10 ms 58360 KB Output is correct
27 Correct 11 ms 58780 KB Output is correct
28 Correct 10 ms 58452 KB Output is correct
29 Correct 11 ms 58452 KB Output is correct
30 Correct 10 ms 58196 KB Output is correct
31 Correct 10 ms 58196 KB Output is correct
32 Correct 11 ms 58340 KB Output is correct
33 Correct 10 ms 58196 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 58108 KB Output is correct
2 Correct 7 ms 57940 KB Output is correct
3 Correct 7 ms 57940 KB Output is correct
4 Correct 7 ms 57940 KB Output is correct
5 Correct 10 ms 57940 KB Output is correct
6 Correct 7 ms 58108 KB Output is correct
7 Correct 9 ms 57940 KB Output is correct
8 Correct 8 ms 58064 KB Output is correct
9 Correct 8 ms 57940 KB Output is correct
10 Correct 8 ms 57940 KB Output is correct
11 Correct 7 ms 57940 KB Output is correct
12 Correct 7 ms 57940 KB Output is correct
13 Correct 8 ms 58116 KB Output is correct
14 Correct 7 ms 57940 KB Output is correct
15 Correct 8 ms 58016 KB Output is correct
16 Correct 7 ms 57940 KB Output is correct
17 Correct 8 ms 57952 KB Output is correct
18 Correct 9 ms 58308 KB Output is correct
19 Correct 10 ms 58616 KB Output is correct
20 Correct 9 ms 58452 KB Output is correct
21 Correct 10 ms 58288 KB Output is correct
22 Correct 9 ms 58452 KB Output is correct
23 Correct 10 ms 58484 KB Output is correct
24 Correct 10 ms 58452 KB Output is correct
25 Correct 108 ms 75084 KB Output is correct
26 Correct 93 ms 81316 KB Output is correct
27 Correct 95 ms 81300 KB Output is correct
28 Correct 175 ms 80728 KB Output is correct
29 Correct 159 ms 75200 KB Output is correct
30 Correct 163 ms 79116 KB Output is correct
31 Correct 139 ms 77904 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 57940 KB Output is correct
2 Correct 9 ms 57940 KB Output is correct
3 Correct 146 ms 68784 KB Output is correct
4 Correct 137 ms 68712 KB Output is correct
5 Correct 151 ms 68768 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 58108 KB Output is correct
2 Correct 7 ms 57940 KB Output is correct
3 Correct 7 ms 57940 KB Output is correct
4 Correct 7 ms 57940 KB Output is correct
5 Correct 10 ms 57940 KB Output is correct
6 Correct 7 ms 58108 KB Output is correct
7 Correct 9 ms 57940 KB Output is correct
8 Correct 8 ms 58064 KB Output is correct
9 Correct 8 ms 57940 KB Output is correct
10 Correct 8 ms 57940 KB Output is correct
11 Correct 7 ms 57940 KB Output is correct
12 Correct 7 ms 57940 KB Output is correct
13 Correct 8 ms 58116 KB Output is correct
14 Correct 7 ms 57940 KB Output is correct
15 Correct 8 ms 58016 KB Output is correct
16 Correct 7 ms 57940 KB Output is correct
17 Correct 8 ms 57952 KB Output is correct
18 Correct 9 ms 58308 KB Output is correct
19 Correct 10 ms 58616 KB Output is correct
20 Correct 9 ms 58452 KB Output is correct
21 Correct 10 ms 58288 KB Output is correct
22 Correct 9 ms 58452 KB Output is correct
23 Correct 10 ms 58484 KB Output is correct
24 Correct 10 ms 58452 KB Output is correct
25 Correct 8 ms 58020 KB Output is correct
26 Correct 10 ms 58360 KB Output is correct
27 Correct 11 ms 58780 KB Output is correct
28 Correct 10 ms 58452 KB Output is correct
29 Correct 11 ms 58452 KB Output is correct
30 Correct 10 ms 58196 KB Output is correct
31 Correct 10 ms 58196 KB Output is correct
32 Correct 11 ms 58340 KB Output is correct
33 Correct 10 ms 58196 KB Output is correct
34 Correct 108 ms 75084 KB Output is correct
35 Correct 93 ms 81316 KB Output is correct
36 Correct 95 ms 81300 KB Output is correct
37 Correct 175 ms 80728 KB Output is correct
38 Correct 159 ms 75200 KB Output is correct
39 Correct 163 ms 79116 KB Output is correct
40 Correct 139 ms 77904 KB Output is correct
41 Correct 8 ms 57940 KB Output is correct
42 Correct 9 ms 57940 KB Output is correct
43 Correct 146 ms 68784 KB Output is correct
44 Correct 137 ms 68712 KB Output is correct
45 Correct 151 ms 68768 KB Output is correct
46 Correct 125 ms 77576 KB Output is correct
47 Correct 115 ms 77644 KB Output is correct
48 Correct 104 ms 77588 KB Output is correct
49 Correct 106 ms 77700 KB Output is correct
50 Correct 114 ms 68944 KB Output is correct
51 Correct 137 ms 68872 KB Output is correct
52 Correct 114 ms 68940 KB Output is correct
53 Correct 144 ms 68940 KB Output is correct