제출 #944975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
944975		IBory	Tourism (JOI23_tourism)	C++17	28 / 100	5087 ms	20816 KiB

tourism

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

const int MAX = 100007, SQ = 8;
int D[MAX], S[MAX], P[17][MAX], in[MAX], pin[MAX], cnt[MAX], ans[MAX], dn, edge;
vector<int> G[MAX];
set<int> A;

struct Query {
	int s, e, id;
	Query(int a = 0, int b = 0, int c = 0) {
		s = a, e = b, id = c;
	}
	const bool operator<(Query& a) {
		if ((s >> SQ) != (a.s >> SQ)) return (s >> SQ) < (a.s >> SQ);
		return e > a.e;
	}
} QS[MAX];

void DFS(int cur, int prev) {
	P[0][cur] = prev;
	D[cur] = D[prev] + 1;
	in[cur] = ++dn;
	pin[dn] = cur;
	for (int next : G[cur]) {
		if (next == prev) continue;
		DFS(next, cur);
	}
}

int LCA(int a, int b) {
	if (D[a] > D[b]) swap(a, b);
	for (int i = 16; i >= 0; --i) if ((D[b] - D[a]) & (1 << i)) b = P[i][b];
	if (a == b) return a;
	for (int i = 16; i >= 0; --i) {
		if (P[i][a] == P[i][b]) continue;
		a = P[i][a], b = P[i][b];
	}
	return P[0][a];
}

void Add(int idx) {
	if (!cnt[S[idx]]++) {
		int n = in[S[idx]];
		auto it = A.lower_bound(n);

		int a = (it != A.begin() ? *prev(it) : 0);
		int b = (it != A.end() ? *it : 0);
		if (a && b) edge += D[LCA(pin[a], pin[b])];
		
		it = A.insert(it, n);
		edge += D[S[idx]];
		if (a) edge -= D[LCA(pin[a], S[idx])];
		if (b) edge -= D[LCA(pin[b], S[idx])];
	}
}

void Sub(int idx) {
	if (!--cnt[S[idx]]) {
		int n = in[S[idx]];
		auto it = A.lower_bound(n);

		int a = (it != A.begin() ? *prev(it) : 0);
		int b = (next(it) != A.end() ? *next(it) : 0);
		if (a && b) edge -= D[LCA(pin[a], pin[b])];
		
		A.erase(n);
		edge -= D[S[idx]];
		if (a) edge += D[LCA(pin[a], S[idx])];
		if (b) edge += D[LCA(pin[b], S[idx])];
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M, Q;
	cin >> N >> M >> Q;
	for (int i = 1; i < N; ++i) {
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	for (int i = 1; i <= M; ++i) cin >> S[i];
	for (int i = 0; i < Q; ++i) {
		int s, e;
		cin >> s >> e;
		QS[i] = Query(s, e, i);
	}
	sort(QS, QS + Q);

	DFS(1, 0);
	for (int n = 1; n < 17; ++n) for (int i = 1; i <= N; ++i) P[n][i] = P[n - 1][P[n - 1][i]];

	int L = 1, R = 0;
	for (int d = 0; d < Q; ++d) {
		auto [s, e, id] = QS[d];
		while (R < e) Add(++R);
		while (s < L) Add(--L);
		while (e < R) Sub(R--);
		while (L < s) Sub(L++);
		ans[id] = edge - D[LCA(pin[*A.begin()], pin[*A.rbegin()])] + 1;
	}

	for (int i = 0; i < Q; ++i) cout << ans[i] << '\n';
	return 0;
}

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