Submission #1231471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231471		k1r1t0	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	161 ms	61940 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 210000;
const int LOGN = 20;

int n, p[N], dep[N], jmp[N][LOGN];
vector<int> g[N];

void dfs(int v, int p = -1) {
	dep[v] = (p == -1 ? 0 : dep[p] + 1);
	jmp[v][0] = (p == -1 ? v : p);
	for (int k = 1; k < LOGN; k++)
		jmp[v][k] = jmp[jmp[v][k - 1]][k - 1];
	for (int u : g[v]) if (u != p)
		dfs(u, v);
}

int dist(int u, int v) {
	int ans = 0;
	if (dep[u] < dep[v])
		swap(u, v);
	for (int k = LOGN - 1; k >= 0; k--)
		if (dep[u] - (1 << k) >= dep[v]) {
			ans += (1 << k);
			u = jmp[u][k];
		}
	if (u == v) return ans;
	for (int k = LOGN - 1; k >= 0; k--)
		if (jmp[u][k] != jmp[v][k]) {
			ans += (2 << k);
			u = jmp[u][k];
			v = jmp[v][k];
		}
	return ans + 2;
}

bool used[N];

struct dsu {
	vector<int> p, s, t, v;
	dsu(int n) {
		p = s = t = v = vector<int>(n + 1);
		for (int i = 1; i <= n; i++) {
			p[i] = i;
			s[i] = 1;
			t[i] = 0;
			v[i] = i;
		}
	}
	int getp(int x) {return p[x] == x ? x : p[x] = getp(p[x]);}
	void unite(int a, int b) {
		a = getp(a);
		b = getp(b);
		if (a == b) return;
		if (s[a] < s[b]) swap(a, b);
		s[a] += s[b];
		p[b] = a;
		t[a] = max(t[a], t[b]);
	}
};

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x; cin >> x;
		p[x] = i;
	}
	for (int i = 1; i <= n - 1; i++) {
		int a, b; cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1);
	dsu cur(n);
	for (int i = 1; i <= n; i++) {
		int opt = 0;
		for (int u : g[p[i]])
			if (used[u])
				opt = max(opt, cur.t[cur.getp(u)] + dist(cur.v[cur.getp(u)], p[i]));
		cur.t[p[i]] = opt;
		for (int u : g[p[i]])
			if (used[u])
				cur.unite(p[i], u);
		cur.v[cur.getp(p[i])] = p[i];
		used[p[i]] = true;
	}
	cout << cur.t[cur.getp(1)];
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26