Submission #1271335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271335		MateiKing80	Tourism (JOI23_tourism)	C++20	100 / 100	877 ms	30848 KiB

tourism

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
vector<int> vec[N];
int sz[N], heavyHead[N], heavyOrd[N], posHeavy[N], depth[N], lift[20][N], timer = 0, tin[N], tout[N];

bool isAncestor(int u, int v) {
	return u == 0 || (tin[u] <= tin[v] && tout[v] <= tout[u]);
}

int lca(int u, int v) {
	if (depth[u] > depth[v])
		swap(u, v);
	for (int bit = 19; bit >= 0; bit --)
		if (depth[lift[bit][v]] >= depth[u])
			v = lift[bit][v];
	if (u == v)
		return u;
	for (int bit = 19; bit >= 0; bit --)
		if (lift[bit][v] != lift[bit][u]) {
			v = lift[bit][v];
			u = lift[bit][u];
		}
	return lift[0][v];
}

struct ura {
	int l, r, time;
	bool operator < (const ura &oth) const {
		return l < oth.l;
	}
};

int aib[N];

inline int lsb(int x) {
	return x & -x;
}

void update(int pos, int val) {
	while (pos < N) {
		aib[pos] += val;
		pos += lsb(pos);
	}
}

int query(int pos) {
	int ans = 0;
	while (pos) {
		ans += aib[pos];
		pos -= lsb(pos);
	}
	return ans;
}

set<ura> s;

void updateInterval(int l, int r, int time) {
	while (1) {
		auto it = s.lower_bound({l, r, time});
		if (it == s.end() || (*it).l > r) {
			if (it == s.begin())
				break;
			it --;
			if ((*it).r < l)
				break;
		}
		auto x = *it;
		update(x.time, -(x.r - x.l + 1));
		s.erase(x);
		if (x.l < l) {
			update(x.time, l - x.l);
			s.insert({x.l, l - 1, x.time});
		}
		if (x.r > r) {
			update(x.time, x.r - r);
			s.insert({r + 1, x.r, x.time});
		}
	}
	update(time, r - l + 1);
	s.insert({l, r, time});
}

void updateHeavy(int u, int v, int time) {
	int x = lca(u, v);
	for (int skib = 0; skib < 2; skib ++) {
		swap(u, v);
		int nu = u;
		while (!isAncestor(u, v)) {
			updateInterval(max(posHeavy[heavyHead[u]], posHeavy[x] + 1), posHeavy[u], time);
			u = lift[0][heavyHead[u]];
		}
		u = nu;
	}
}

void dfsSz(int nod, int papa) {
	depth[nod] = 1 + depth[papa];
	lift[0][nod] = papa;
	for (int i = 1; i < 20; i ++)
		lift[i][nod] = lift[i - 1][lift[i - 1][nod]];
	sz[nod] = 1;
	for (auto i : vec[nod]) {
		if (i == papa)
			continue;
		dfsSz(i, nod);
		sz[nod] += sz[i];
	}
}

void dfsHeavy(int nod, int papa, int value) {
	heavyHead[nod] = value;
	heavyOrd[++timer] = nod;
	tin[nod] = timer;
	for (int i = 0; i < (int)vec[nod].size(); i ++)
		if (vec[nod][i] == papa)
			swap(vec[nod][i], vec[nod][vec[nod].size() - 1]);
	for (int i = 1; i < (int)vec[nod].size(); i ++) {
		if (vec[nod][i] == papa)
			continue;
		if (sz[vec[nod][0]] < sz[vec[nod][i]])
			swap(vec[nod][i], vec[nod][0]);
	}
	if (vec[nod].size() && vec[nod][0] != papa)
		dfsHeavy(vec[nod][0], nod, heavyHead[nod]);
	for (int i = 1; i < (int)vec[nod].size(); i ++)
		if (vec[nod][i] != papa)
			dfsHeavy(vec[nod][i], nod, vec[nod][i]);
	tout[nod] = timer;
}

signed main() {
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1; i < n; i ++) {
		int u, v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	dfsSz(1, 0);
	dfsHeavy(1, 0, 1);
	for (int i = 1; i <= n; i ++)
		posHeavy[heavyOrd[i]] = i;
	vector<int> v(m + 1);
	for (int i = 1; i <= m; i ++)
		cin >> v[i];
	vector<vector<int>> qrs(m + 1);
	vector<pair<int, int>> qq(q);
	vector<int> ans(q);
	for (int i = 0; i < q; i ++) {
		int l, r;
		cin >> l >> r;
		qq[i] = {l, r};
		qrs[r].push_back(i);
		if (l == 1 && r == 1)
			ans[i] = 1;
	}
	for (int i = 2; i <= m; i ++) {
		updateHeavy(v[i - 1], v[i], i - 1);
		for (auto j : qrs[i])
			ans[j] = query(i) - query(qq[j].first - 1) + 1;
	}
	for (auto &i : ans)
		cout << 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