Submission #919471

#	Time	Username	Problem	Language	Result	Execution time	Memory
919471		OAleksa	Tourism (JOI23_tourism)	C++14	34 / 100	5053 ms	27508 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 1e5 + 69;
int n, m, q, c[N], ans[N], sz[N], top[N], pos[N], fenw[N];
int node, par[N], dep[N];
vector<int> g[N];
vector<pair<int, int>> qs[N];
set<tuple<int, int, int>> range;
void modify(int v, int val) {
	for (int i = v;i < N;i += (i & -i))
		fenw[i] += val;
}
int Get(int v) {
	int r = 0;
	for (int i = v;i > 0;i -= (i & -i))
		r += fenw[i];
	return r;
}
void dfs(int v, int p) {
	sz[v] = 1;
	par[v] = p;
	dep[v] = dep[p] + 1;
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
		sz[v] += sz[u];
	}
}
void hld(int v, int p, int tp) {
	pos[v] = ++node;
	top[v] = tp;
	int s = -1, mx = 0;
	for (auto u : g[v]) {
		if (u == p)
			continue;
		if (sz[u] > mx) {
			mx = sz[u];
			s = u;
		}
	}
	if (s == -1)
		return;
	hld(s, v, tp);
	for (auto u : g[v]) {
		if (u == s || u == p)
			continue;
		hld(u, v, u);
	}
}
void Modify(int l, int r, int c) {
	if (l > r)
		swap(l, r);
	while (l <= r) {
		auto u = range.upper_bound({l, N, -1});
		--u;
		int levo, desno, clr;
		tie(levo, desno, clr) = *u;
		int cnt = 0;
		range.erase(u);
		if (l > levo) 
			range.insert({levo, l - 1, clr});
		if (desno > r)
			range.insert({r + 1, desno, clr});
		cnt += min(desno, r) - l + 1;
		modify(clr, -cnt);
		modify(c, min(desno, r) - l + 1);
		range.insert({l, min(desno, r), c});
		l = desno + 1;
	}
}
void Change(int a, int b, int c) {
	while (top[a] != top[b]) {
		if (dep[top[a]] < dep[top[b]])
			swap(a, b);
		Modify(pos[top[a]], pos[a], c);
		a = par[top[a]];
	}
	Modify(pos[b], pos[a], c);
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> m >> q;
  	for (int i = 1;i <= n - 1;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 >> c[i];
  	for (int i = 1;i <= q;i++) {
  		int l, r;
  		cin >> l >> r;
  		qs[r].push_back({l, i});
  	}
  	dfs(1, 0);
  	hld(1, 1, 1);
  	range.insert({1, n, N});
  	for (int i = 1;i <= m;i++) {
  		if (i > 1) 
  			Change(c[i], c[i - 1], i - 1);
  		for (auto u : qs[i]) {
  			int l, ind;
  			tie(l, ind) = u;
  			if (l == i)
  				ans[ind] = 1;
  			else
  				ans[ind] = Get(N - 1) - Get(l - 1);
  		}
  	}
  	for (int i = 1;i <= q;i++)
  		cout << ans[i] << '\n';
	}
  return 0;
}

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