oj.uz

Submission #851502

# Submission time Handle Problem Language Result Execution time Memory
851502 2023-09-20T02:35:48 Z IBory Tourism (JOI23_tourism) C++17
0 / 100
 5000 ms 23708 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int SZ = 1 << 17, MAX = 100007;
vector<int> G[MAX], TG[MAX];
int in[MAX], out[MAX], P[MAX], Z[MAX], H[MAX], top[MAX], dn;
int C[MAX], ans[MAX];

void DFS1(int cur, int prev) {
	P[cur] = prev;
	in[cur] = ++dn;
	for (int next : TG[cur]) {
		if (next == prev) continue;
		G[cur].push_back(next);
		DFS1(next, cur);
	}
	out[cur] = dn;
}

int DFS2(int cur) {
	int& ret = Z[cur] = 1;
	for (int& next : G[cur]) {
		H[next] = H[cur] + 1;
		ret += DFS2(next);
		if (Z[next] > Z[G[cur][0]]) swap(next, G[cur][0]);
	}
	return ret;
}

void DFS3(int cur) {
	for (int next : G[cur]) {
		top[next] = (next == G[cur][0] ? top[cur] : next);
		DFS3(next);
	}
}

struct Seg {
	pii T[SZ << 1];
	int Z[SZ << 1];

	void Init(int N) {
		for (int i = 1; i <= N; ++i) T[i + SZ - 1] = {0, 1};
		for (int i = SZ - 1; i > 0; --i) T[i] = Merge(T[i * 2], T[i * 2 + 1]);
	}

	pii Merge(pii a, pii b) {
		if (a.first != b.first) return min(a, b);
		return {a.first, a.second + b.second};
	}

	void Push(int n) {
		if (!Z[n]) return;
		if (n < SZ) {
			Z[n * 2] += Z[n];
			Z[n * 2 + 1] += Z[n];
		}
		T[n].first += Z[n];
		Z[n] = 0;
	}

	void Update(int L, int R, int v, int sL = 1, int sR = SZ, int n = 1) {
		Push(n);
		if (R < sL || sR < L) return;
		if (L <= sL && sR <= R) {
			Z[n] += v;
			Push(n);
			return;
		}
		int mid = (sL + sR) >> 1;
		Update(L, R, v, sL, mid, n * 2);
		Update(L, R, v, mid + 1, sR, n * 2 + 1);
		T[n] = Merge(T[n * 2], T[n * 2 + 1]);
	}

	pii Query(int L, int R, int sL = 1, int sR = SZ, int n = 1) {
		Push(n);
		if (R < sL || sR < L) return {1 << 30, 0};
		if (L <= sL && sR <= R) return T[n];
		int mid = (sL + sR) >> 1;
		return Merge(Query(L, R, sL, mid, n * 2), Query(L, R, mid + 1, sR, n * 2 + 1));
	}

	void PathUpdate(int a, int b, int v) {
		while (top[a] != top[b]) {
			if (top[a] > top[b]) swap(a, b);
			Update(in[top[b]], in[b], v);
			b = P[top[b]];
		}
		if (H[a] > H[b]) swap(a, b);
		Update(in[a], in[b], v);
	}
} T;

int LCA(int a, int b) {
	if (!min(a, b)) return max(a, b);
	while (top[a] != top[b]) {
		if (top[a] > top[b]) swap(a, b);
		b = P[top[b]];
	}
	return (H[a] > H[b] ? b : a);
}

struct Seg2 {
	int T[SZ << 1];
	
	void Build() {
		for (int i = SZ - 1; i > 0; --i) T[i] = LCA(T[i * 2], T[i * 2 + 1]);
	}

	int Query(int L, int R, int sL = 1, int sR = SZ, int n = 1) {
		if (R < sL || sR < L) return 0;
		if (L <= sL && sR <= R) return T[n];
		int mid = (sL + sR) >> 1;
		return LCA(Query(L, R, sL, mid, n * 2), Query(L, R, mid + 1, sR, n * 2 + 1));
	}
} T2;

void Add(int n) {
	T.PathUpdate(1, C[n], 1);
}

void Sub(int n) {
	T.PathUpdate(1, C[n], -1);
}

struct Query {
	int s, e, id;
	Query(int s = 0, int e = 0, int id = 0) : s(s), e(e), id(id) {};
	bool operator<(const Query& a) {
		if ((s >> 8) != (a.s >> 8)) return (s >> 8) < (a.s >> 8);
		return e < a.e;
	}
};

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;
		TG[a].push_back(b);
		TG[b].push_back(a);
	}

	DFS1(1, 0);
	DFS2(1);
	top[1] = 1; DFS3(1);

	for (int i = 1; i <= M; ++i) {
		cin >> C[i];
		T2.T[SZ + i - 1] = C[i];
	}
	T2.Build();

	vector<Query> A;
	for (int i = 0; i < Q; ++i) {
		int l, r;
		cin >> l >> r;
		A.push_back(Query(l, r, i));
	}
	sort(A.begin(), A.end());

	T.Init(N);
	int L = 1, R = 0;
	for (auto [l, r, id] : A) {
		while (R < r) Add(++R);
		while (r < R) Sub(R--);
		while (l < L) Add(--L);
		while (L < l) Sub(L++);
		int root = T2.Query(l, r), cur = out[root] - in[root] + 1;
		pii p = T.Query(in[root], out[root]);
		if (!p.first) cur -= p.second;
		ans[id] = cur;
	}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12380 KB Output is correct
2 Correct 3 ms 12200 KB Output is correct
3 Correct 3 ms 12376 KB Output is correct
4 Incorrect 10 ms 12376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12380 KB Output is correct
2 Correct 3 ms 12200 KB Output is correct
3 Correct 3 ms 12376 KB Output is correct
4 Incorrect 10 ms 12376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12376 KB Output is correct
2 Correct 6 ms 12224 KB Output is correct
3 Correct 29 ms 12380 KB Output is correct
4 Execution timed out 5009 ms 23708 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12376 KB Output is correct
2 Incorrect 157 ms 16024 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12376 KB Output is correct
2 Correct 7 ms 12376 KB Output is correct
3 Correct 29 ms 12456 KB Output is correct
4 Execution timed out 5040 ms 18632 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12380 KB Output is correct
2 Correct 3 ms 12200 KB Output is correct
3 Correct 3 ms 12376 KB Output is correct
4 Incorrect 10 ms 12376 KB Output isn't correct
5 Halted 0 ms 0 KB -