Submission #1152121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152121		AmirAli_H1	Tourism (JOI23_tourism)	C++20	100 / 100	502 ms	33516 KiB

tourism

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = (1 << 17) + 4;
const int maxlg = 18;

int n, m, q;
vector<int> adj[maxn]; vector<pii> Q[maxn];
int up[maxn][maxlg], A[maxn], ans[maxn];
int h[maxn], sz[maxn], hld[maxn];
int st[maxn], ft[maxn], timer, ind[maxn];
int M[maxn], cnt[maxn]; vector<int> ls;
ll tx[maxn]; pii t[2 * maxn];

bool cmp(int i, int j) {
	return (sz[i] > sz[j]);
}

void pre_dfs(int v, int p = -1) {
	up[v][0] = (p != -1) ? p : v;
	for (int i = 1; i < maxlg; i++) up[v][i] = up[up[v][i - 1]][i - 1];
	sz[v] = 1;
	for (int u : adj[v]) {
		if (u == p) continue;
		h[u] = h[v] + 1;
		pre_dfs(u, v);
		sz[v] += sz[u];
	}
}

void res_dfs(int v, int p = -1) {
	st[v] = timer++;
	if (p != -1 && st[p] + 1 == st[v]) hld[v] = hld[p];
	else hld[v] = v;
	for (int u : adj[v]) {
		if (u == p) continue;
		res_dfs(u, v);
	}
	ft[v] = timer;
}

bool is_gr(int v, int u) {
	return (st[v] <= st[u] && ft[v] >= ft[u]);
}

int lca(int u, int v) {
	if (is_gr(u, v)) return u;
	if (is_gr(v, u)) return v;
	for (int i = maxlg - 1; i >= 0; i--) {
		if (!is_gr(up[u][i], v)) u = up[u][i];
	}
	return up[u][0];
}

void addx(int i, ll x) {
	for (++i; i <= m; i += (i & -i)) tx[i] += x;
}

ll getx(int i) {
	ll res = 0;
	for (++i; i > 0; i -= (i & -i)) res += tx[i];
	return res;
}

pii f(pii a, pii b) {
	pii res; res.F = -1;
	if (a.S == -1 || b.S == -1 || a.S != b.S) res.S = -1;
	else res.S = a.S;
	return res;
}

void shift(int v, int tl, int tr) {
	int x = t[v].F; t[v].F = -1;
	if (x == -1 || tr - tl == 1) return ;
	t[2 * v + 1].F = t[2 * v + 1].S = x;
	t[2 * v + 2].F = t[2 * v + 2].S = x;
}

void build(int v, int tl, int tr) {
	t[v].F = -1;
	if (tr - tl == 1) {
		t[v].S = m;
		return ;
	}
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
	t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}

void set_val(int v, int tl, int tr, int l, int r, int x) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ;
	shift(v, tl, tr);
	if (l == tl && r == tr && t[v].S != -1) {
		if (!M[x]) {
			M[x] = 1; ls.pb(x);
		}
		if (!M[t[v].S]) {
			M[t[v].S] = 1; ls.pb(t[v].S);
		}
		cnt[x] += (tr - tl); cnt[t[v].S] -= (tr - tl);
		t[v].F = t[v].S = x;
		return ;
	}
	int mid = (tl + tr) / 2;
	set_val(2 * v + 1, tl, mid, l, r, x); set_val(2 * v + 2, mid, tr, l, r, x);
	t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}

void setx(int v, int r, int j) {
	while (h[v] > h[r]) {
		set_val(0, 0, n, max(st[r] + 1, st[hld[v]]), st[v] + 1, j);
		v = up[hld[v]][0];
	}
	for (int x : ls) {
		addx(x, cnt[x]);
		M[x] = 0; cnt[x] = 0;
	}
	ls.clear();
}

void solve() {
	cin >> n >> m >> q;
	for (int i = 0; i < n; i++) adj[i].clear();
	for (int i = 0; i < m; i++) Q[i].clear();
	fill(ans, ans + q, 1);
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v; u--; v--;
		adj[u].pb(v); adj[v].pb(u);
	}
	for (int i = 0; i < m; i++) {
		cin >> A[i]; A[i]--;
	}
	for (int i = 0; i < q; i++) {
		int l, r;
		cin >> l >> r; l--; r--;
		Q[l].pb(Mp(r, i));
	}

	pre_dfs(0);
	for (int i = 0; i < n; i++) sort(all(adj[i]), cmp);
	timer = 0; res_dfs(0);

	fill(tx, tx + (m + 1), 0); build(0, 0, n);
	fill(M, M + (m + 1), 0); fill(cnt, cnt + (m + 1), 0); ls.clear();
	for (int i = m - 1; i >= 0; i--) {
		if (i + 1 < m) {
			int u = A[i], v = A[i + 1];
			int r = lca(u, v);
			setx(u, r, i + 1); setx(v, r, i + 1);
		}
		for (auto f : Q[i]) {
			int r = f.F, j = f.S;
			ans[j] = getx(r) + 1;
		}
	}
	for (int i = 0; i < q; i++) cout << ans[i] << endl;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int T = 1;
	while (T--) {
		solve();
	}
	
	return 0;
}

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