Submission #1227066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227066		chaeryeong	Tourism (JOI23_tourism)	C++20	100 / 100	4264 ms	31220 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 1;
const int B = 18;
vector <int> adj[N];
int n, m, q, ans[N], p[N], sze[N], in[N], nxt[N], tt, dep[N], a[N], dp[B][N];
vector <pair <int, int>> queries[N];
void dfs1 (int pos, int par) {
	p[pos] = par;
	dp[0][pos] = p[pos];
	for (int i = 1; i < B; i++) {
		dp[i][pos] = dp[i - 1][dp[i - 1][pos]];
	}
	if (par != 0) {
		adj[pos].erase(find(adj[pos].begin(), adj[pos].end(), par));
	}
	sze[pos] = 1;
	for (auto &j : adj[pos]) {
		dep[j] = 1 + dep[pos];
		dfs1(j, pos);
		sze[pos] += sze[j];
		if (sze[j] > sze[adj[pos][0]]) {
			swap(j, adj[pos][0]);
		}
	}
}
void dfs2 (int pos) {
	in[pos] = ++tt;
	for (auto j : adj[pos]) {
		nxt[j] = (j == adj[pos][0] ? nxt[pos] : j);
		dfs2(j);
	}
}
int highest[N];
#define mid ((l + r) >> 1)
#define tl (node << 1)
#define tr (node << 1 | 1)
struct SegmentTree {
	int tree[N << 2], lazy[N << 2];
	void prop (int l, int r, int node) {
		if (lazy[node] == 0) {
			return;
		}
		if (l != r) {
			for (auto x : {tl, tr}) {
				lazy[x] = lazy[node];
			}
		}
		tree[node] = lazy[node];
		lazy[node] = 0;
	}
	void update (int l, int r, int a, int b, int c, int node) {
		prop(l, r, node);
		if (l > b || r < a) return;
		if (l >= a && r <= b) {
			lazy[node] = c;
			prop(l, r, node);
			return;
		}
		update(l, mid, a, b, c, tl); update(mid + 1, r, a, b, c, tr);
	}
	int get (int l, int r, int a, int node) {
		prop(l, r, node);
		if (l == r) {
			return tree[node];
		}
		if (a <= mid) {
			return get(l, mid, a, tl);
		} else {
			return get(mid + 1, r, a, tr);
		}
	}
} cur;
void set_path (int u, int v, int w) {
	while (nxt[v] != nxt[u]) {
		cur.update(1, n, in[nxt[v]], in[v], w, 1);
		v = p[nxt[v]];
	}
	cur.update(1, n, in[u], in[v], w, 1);
}
int lca (int x, int y) {
	if (dep[x] > dep[y]) {
		swap(x, y);
	}
	for (int i = B - 1; i >= 0; i--) {
		if ((dep[y] - dep[x]) & (1 << i)) {
			y = dp[i][y];
		}
	}
	if (x == y) {
		return x;
	}
	for (int i = B - 1; i >= 0; i--) {
		if (dp[i][x] != dp[i][y]) {
			x = dp[i][x], y = dp[i][y];
		}
	}
	return p[x];
}
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> q;
	for (int i = 1; i < n; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs1(1, 0);
	nxt[1] = 1;
	dfs2(1);
	for (int i = 1; i <= m; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= q; i++) {
		int l, r; cin >> l >> r;
		queries[r].push_back({l, i});
	}
	for (int i = 1; i <= n; i++) {
		cur.update(1, n, in[i], in[i], -1, 1);
	}
	memset(highest, -1, sizeof(highest));
	vector <int> pp(m + 1, 0);
	vector <int> mxs, mns;
	for (int i = 1; i <= m; i++) {
		while (!mxs.empty() && in[a[mxs.back()]] < in[a[i]]) {
			mxs.pop_back();
		}
		mxs.push_back(i);
		while (!mns.empty() && in[a[mns.back()]] > in[a[i]]) {
			mns.pop_back();
		}
		mns.push_back(i);
		int u = a[i];
		while (true) {
			int z = cur.get(1, n, in[u], 1);
			if (z == -1) {
				if (u == 1) {
					break;
				}
				u = p[u];
				continue;
			}
			int y = highest[z];
			pp[z] -= (dep[u] - dep[y] + 1);
			if (a[z] == u) {
				highest[z] = -1;
			} else {
				int x = a[z];
				for (int j = B - 1; j >= 0; j--) {
					if (dp[j][x] != 0 && dep[dp[j][x]] > dep[u]) {
						x = dp[j][x];
					}
				}
				highest[z] = x;
			}
			if (y == 1) {
				break;
			}
			u = p[y];
		}	
		set_path(1, a[i], i);
		highest[i] = 1;
		pp[i] += dep[a[i]] + 1;
		for (auto [x, y] : queries[i]) {
			auto g = *lower_bound(mns.begin(), mns.end(), x);
			auto f = *lower_bound(mxs.begin(), mxs.end(), x);
			g = a[g]; f = a[f];
			int z = lca(g, f);
			ans[y] -= dep[z];
			for (int j = x; j <= i; j++) {
				ans[y] += pp[j];
			}
		}
	}
	for (int i = 1; i <= q; i++) {
		cout << ans[i] << '\n';
	}
}	

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