제출 #743876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
743876		pavement	Tourism (JOI23_tourism)	C++17	0 / 100	20 ms	25176 KiB

tourism

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define mt make_tuple

using ii = pair<int, int>;
using iiii = tuple<int, int, int, int>;

const int BLK_SZ = 3;
int N, M, Q, wL, wR = -1, idx, cur, sv_cur, out[100005], C[100005], L[100005], R[100005], pre[100005], dep[100005], ll[100005], rr[100005], anc[25][100005];
iiii T[100005];
vector<int> adj[100005];
multiset<ii> S;

void dfs(int n, int e = -1) {
	pre[n] = ++idx;
	for (int k = 1; k <= 20; k++) {
		if (anc[k - 1][n] == -1) break;
		anc[k][n] = anc[k - 1][anc[k - 1][n]];
	}
	for (auto u : adj[n]) if (u != e) {
		anc[0][u] = n;
		dep[u] = dep[n] + 1;
		dfs(u, n);
	}
}

int lca(int u, int v) {
	if (dep[u] > dep[v]) swap(u, v);
	for (int k = 20; k >= 0; k--) {
		if (dep[v] - (1 << k) >= dep[u]) {
			v = anc[k][v];
		}
	}
	if (u == v) return u;
	for (int k = 20; k >= 0; k--) {
		if (anc[k][u] != anc[k][v]) {
			u = anc[k][u];
			v = anc[k][v];
		}
	}
	return anc[0][u];
}

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

void add_path(int u, int v) {
	//~ cout << " + " << u << ' ' << v << '\n';
	cur += dist(u, v);
}

void rem_path(int u, int v) {
	//~ cout << " - " << u << ' ' << v << '\n';
	cur -= dist(u, v);	
}

void add(int k) {
	//~ cout << "ADD " << k << '\n';
	S.emplace(pre[k], k);
	auto it = S.find(mp(pre[k], k));
	ii x = mp(-1, -1), y = mp(-1, -1);
	if (it != S.begin()) {
		--it;
		x = *it;
		++it;
	}
	++it;
	if (it != S.end()) {
		y = *it;
	}
	--it;
	//~ cout << "! " << x.second << ' ' << y.second << '\n';
	if (x.first != -1 && y.first != -1) {
		rem_path(x.second, y.second);
	} else if (x.first == -1 && y.first != -1) {
		auto it2 = --S.end();
		rem_path(y.second, it2->second);
	} else if (y.first == -1 && x.first != -1) {
		auto it2 = S.begin();
		rem_path(x.second, it2->second);
	}
	if (x.first == -1 && y.first == -1) {}
	else if (x.first == -1) {
		auto it2 = --S.end();
		add_path(it2->second, k);
		add_path(k, y.second);
	} else if (y.first == -1) {
		auto it2 = S.begin();
		add_path(x.second, k);
		add_path(k, it2->second);
	} else {
		add_path(x.second, k);
		add_path(k, y.second);
	}
}

void rem(int k) {
	S.erase(S.find(mp(pre[k], k)));
}

int main() {
	memset(anc, -1, sizeof anc);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M >> Q;
	for (int i = 1; i <= M; i++) {
		if (ll[i / BLK_SZ] == 0) ll[i / BLK_SZ] = i;
		rr[i / BLK_SZ] = i;
	}
	for (int i = 1, u, v; i < N; i++) {
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(1);
	for (int i = 1; i <= M; i++) {
		cin >> C[i];
	}
	for (int i = 1; i <= Q; i++) {
		cin >> L[i] >> R[i];
		T[i] = mt(L[i] / BLK_SZ, R[i], L[i], i);
	}
	sort(T + 1, T + 1 + Q);
	for (int i = 1; i <= Q; i++) {
		auto [_, r, l, idx] = T[i];
		L[i] = l;
		R[i] = r;
		if (L[i] / BLK_SZ == R[i] / BLK_SZ) {
			continue;
		}
		//~ cout << "@  " << L[i] << ' ' << R[i] << '\n';
		// move window to [L[i], R[i]]
		if (wR == -1 || wL / BLK_SZ != L[i] / BLK_SZ) {
			for (int j = wL; j <= wR; j++) rem(C[j]);
			cur = 0;
			//~ cout << "REM ALL " << cur << '\n';
			for (int j = rr[L[i] / BLK_SZ] + 1; j <= R[i]; j++) add(C[j]);
			sv_cur = cur;
			for (int j = rr[L[i] / BLK_SZ]; j >= L[i]; j--) add(C[j]);
			//~ cout << cur << ' ' << get<0>(diam) << ' ' << get<1>(diam) << ' ' << get<2>(diam) << '\n';
			out[idx] = cur / 2 + 1;
			//~ cout << cur / 2 + 1 << '\n';
			for (int j = rr[L[i] / BLK_SZ]; j >= L[i]; j--) rem(C[j]);
			cur = sv_cur;
			wL = L[i];
			wR = R[i];
			continue;
		}
		for (int j = wR + 1; j <= R[i]; j++) add(C[j]);
		sv_cur = cur;
		for (int j = rr[L[i] / BLK_SZ]; j >= L[i]; j--) add(C[j]);
		out[idx] = cur / 2 + 1;
		//~ cout << cur / 2 + 1 << '\n';
		for (int j = rr[L[i] / BLK_SZ]; j >= L[i]; j--) rem(C[j]);
		cur = sv_cur;
		wL = L[i];
		wR = R[i];
	}
	for (int i = wL; i <= wR; i++) rem(C[i]);
	cur = 0;
	for (int i = 1; i <= Q; i++) {
		if (L[i] / BLK_SZ == R[i] / BLK_SZ) {
			for (int j = L[i]; j <= R[i]; j++) add(C[j]);
			out[get<3>(T[i])] = cur / 2 + 1;
			for (int j = L[i]; j <= R[i]; j++) rem(C[j]);
			cur = 0;
		}
	}
	for (int i = 1; i <= Q; i++) {
		cout << out[i] << '\n';
	}
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41