oj.uz

Submission #757733

# Submission time Handle Problem Language Result Execution time Memory
757733 2023-06-13T16:40:23 Z happypotato Tourism (JOI23_tourism) C++17
0 / 100
 5000 ms 42104 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
// global
const int mxN = 1e5 + 1;
int c[mxN];
vector<int> adj[mxN];
pii range[mxN];
pii range2[mxN];
int depth[mxN];
pii lcasp[mxN * 2][20];
map<pii, int> rangeconv;
int tt = 0, tt2 = 0;
int n, m, q;
void DFSInit(int u = 1, int par = -1, int dep = 0) {
	range[u].ff = ++tt;
	lcasp[++tt2][0] = {dep, u};
	range2[u] = {tt2, tt2};
	depth[u] = dep;
	for (int &v : adj[u]) {
		if (v != par) {
			DFSInit(v, u, dep + 1);
			lcasp[++tt2][0] = {dep, u};
			range2[u].ss = tt2;
		}
	}
	range[u].ss = tt;
	rangeconv[range[u]] = u;
}
void InitSparse() {
	for (int dep = 1; dep < 20; dep++) {
		for (int i = 1; i + (1 << dep) - 1 <= tt2; i++) {
			if (lcasp[i][dep - 1].ff < lcasp[i + (1 << (dep - 1))][dep - 1].ff) {
				lcasp[i][dep] = lcasp[i][dep - 1];
			} else {
				lcasp[i][dep] = lcasp[i + (1 << (dep - 1))][dep - 1];
			}
		}
	}
}
int fastlog(int x) {
	return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
int QueryLCA(int lhs, int rhs) {
	// cerr << "QUERY LCA " << lhs << ' ' << rhs << endl;
	int bit = fastlog(rhs - lhs + 1);
	pii resl = lcasp[lhs][bit], resr = lcasp[rhs - (1 << bit) + 1][bit];
	if (resl.ff < resr.ff) return resl.ss;
	else return resr.ss;
}
int dir[mxN];
int freq[mxN];
int indeg[mxN];
bool vis[mxN];
int ans;
int lca;
multiset<int> lefts;
multiset<int, greater<int>> rights;
int BuildTree(int u = 1, int par = -1) {
	vector<int> res;
	for (int &v : adj[u]) {
		if (v != par) {
			int ret = BuildTree(v, u);
			if (ret != -1) {
				res.pb(ret);
			}
		}
	}
	if (res.size() >= 2 || freq[u]) {
		for (int &v : res) {
			dir[v] = u;
			indeg[u]++;
			ans += (depth[v] - depth[u]);
		}
		lefts.insert(range2[u].ff);
		rights.insert(range2[u].ss);
		lca = u;
		return u;
	} else if (res.size() == 1) {
		return res.front();
	} else {
		return -1;
	}
}
int find(int u) {
	return dir[u];
	if (indeg[u]) return u;
	return (dir[u] = find(dir[u]));
}
void SubtractNode(int u) {
	// cerr << "SUBTRACTING " << u << endl;
	freq[u]--;
	if (freq[u]) return;
	if (!indeg[u]) {
		// no children
		ans -= (depth[u] - depth[find(u)]);
		indeg[find(u)]--;
		vis[u] = true;
		lefts.erase(lefts.find(range2[u].ff));
		rights.erase(rights.find(range2[u].ss));
	}
	// cerr << u << ": " << find(u) << endl;

	while (!freq[u] && !indeg[u]) {
		if (!vis[u]) {
			vis[u] = true;
			lefts.erase(lefts.find(range2[u].ff));
			rights.erase(rights.find(range2[u].ss));
		}
		u = dir[u];
	}
	
	int newlca = QueryLCA(*lefts.begin(), *rights.begin());
	while (!vis[newlca] && !freq[newlca] && indeg[newlca] == 1) {
		vis[newlca] = true;
		lefts.erase(lefts.find(range2[newlca].ff));
		rights.erase(rights.find(range2[newlca].ss));
		newlca = QueryLCA(*lefts.begin(), *rights.begin());
	}
	ans -= (depth[newlca] - depth[lca]);
	lca = newlca;
}
int SubtractRange(int l, int r) {
	// cerr << "SUBTRACTING RANGE " << l << ' ' << r << endl;
	// cerr << ans << endl;
	// for (int i = 1; i <= n; i++) {
	// 	cerr << dir[i] << ' ';
	// }
	// cerr << endl;
	// for (int i = 1; i <= n; i++) {
	// 	cerr << indeg[i] << ' ';
	// }
	// cerr << endl;
	// cerr << "LEFT "; for (int x : lefts) cerr << x << ' '; cerr << endl;
	// cerr << "RIGHT "; for (int x : rights) cerr << x << ' '; cerr << endl;

	if (l > r) return ans;
	int nans = ans;
	queue<int> q;
	vector<pii> track;
	vector<int> track2;
	for (int i = l; i <= r; i++) {
		freq[c[i]]--;
		if (!freq[c[i]]) {
			if (!freq[c[i]] && !indeg[c[i]]) {
				q.push(c[i]);
				track2.pb(c[i]);
				vis[c[i]] = true;
				lefts.erase(lefts.find(range2[c[i]].ff));
				rights.erase(rights.find(range2[c[i]].ss));
			}
		}
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		// cerr << u << ' ' << dir[u] << endl;
		nans -= (depth[u] - depth[dir[u]]);
		indeg[dir[u]]--;
		track.pb({dir[u], -1});
		if (!freq[dir[u]] && !indeg[dir[u]]) {
			q.push(dir[u]);
			if (!vis[dir[u]]) {
				track2.pb(dir[u]);
				lefts.erase(lefts.find(range2[dir[u]].ff));
				rights.erase(rights.find(range2[dir[u]].ss));
			}
		}
	}
	// cerr << "LEFT "; for (int x : lefts) cerr << x << ' '; cerr << endl;
	// cerr << "RIGHT "; for (int x : rights) cerr << x << ' '; cerr << endl;
	int newlca = QueryLCA(*lefts.begin(), *rights.begin());
	while (!vis[newlca] && !freq[newlca] && indeg[newlca] == 1) {
		track2.pb(newlca);
		vis[newlca] = true;
		lefts.erase(lefts.find(range2[newlca].ff));
		rights.erase(rights.find(range2[newlca].ss));
		newlca = QueryLCA(*lefts.begin(), *rights.begin());
	}
	// cerr << lca << ' ' << newlca << endl;
	nans -= (depth[newlca] - depth[lca]);
	for (int i = l; i <= r; i++) {
		freq[c[i]]++;
	}
	for (pii &u : track) {
		indeg[u.ff] -= u.ss;
	}
	for (int &u : track2) {
		lefts.insert(range2[u].ff);
		rights.insert(range2[u].ss);
		vis[u] = false;
	}
	return nans;
}
void init() {
	// init

}
const int BLOCK = 1000;
bool cmp(pair<pii, int> &lhs, pair<pii, int> &rhs) {
	if ((lhs.ff.ff - 1) / BLOCK != (rhs.ff.ff - 1) / BLOCK) {
		return ((lhs.ff.ff - 1) / BLOCK) < ((rhs.ff.ff - 1) / BLOCK);
	}
	return lhs.ff.ss > rhs.ff.ss;
}
void solve() {
	// solve
	cin >> n >> m >> q;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	DFSInit();
	InitSparse();
	for (int i = 1; i <= m; i++) cin >> c[i];
	pair<pii, int> queries[q];
	int fin[q];
	for (int i = 0; i < q; i++) {
		cin >> queries[i].ff.ff >> queries[i].ff.ss;
		queries[i].ss = i;
	}
	sort(queries, queries + q, cmp);
	int ptr = 0;
	for (int st = 1; st <= m; st += BLOCK) {
		for (int i = 1; i <= n; i++) {
			indeg[i] = 0;
			dir[i] = 0;
			freq[i] = 0;
			vis[i] = false;
		}
		lefts.clear(); rights.clear();
		ans = 1;
		for (int i = st; i <= m; i++) {
			freq[c[i]]++;
		}
		BuildTree();
		int curptr = m;
		while (ptr < q && queries[ptr].ff.ff <= st + BLOCK - 1) {
			while (curptr > queries[ptr].ff.ss) {
				SubtractNode(c[curptr]);
				curptr--;
			}
			fin[queries[ptr].ss] = SubtractRange(st, queries[ptr].ff.ff - 1);
			ptr++;
		}
	}
	for (int i = 0; i < q; i++) {
		cout << fin[i] << endl;
	}
	// for (int curquery = 1; curquery <= q; curquery++) {
	// 	int l, r;
	// 	cin >> l >> r;
	// 	if (l == r) {
	// 		cout << "1\n";
	// 		continue;
	// 	}
	// 	// cerr << "QUERY " << l << ' ' << r << endl;
	// 	for (int i = 1; i <= n; i++) {
	// 		indeg[i] = 0;
	// 		dir[i] = 0;
	// 		freq[i] = 0;
	// 		vis[i] = false;
	// 	}
	// 	lefts.clear(); rights.clear();
	// 	ans = 1;
	// 	for (int i = 1; i <= r; i++) {
	// 		freq[c[i]]++;
	// 	}
	// 	BuildTree();
	// 	// cerr << ans << endl;
	// 	// for (int i = 1; i <= n; i++) {
	// 	// 	cerr << dir[i] << ' ';
	// 	// }
	// 	// cerr << endl;
	// 	// for (int i = 1; i <= n; i++) {
	// 	// 	cerr << indeg[i] << ' ';
	// 	// }
	// 	// cerr << endl;
	// 	// cerr << "LEFT "; for (int x : lefts) cerr << x << ' '; cerr << endl;
	// 	// cerr << "RIGHT "; for (int x : rights) cerr << x << ' '; cerr << endl;
	// 	cout << SubtractRange(1, l - 1) << endl;
	// }
}
int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	init(); solve();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2692 KB Output is correct
4 Incorrect 4 ms 2688 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2692 KB Output is correct
4 Incorrect 4 ms 2688 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2692 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 10 ms 2772 KB Output is correct
4 Incorrect 2095 ms 42104 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2445 ms 31636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 11 ms 2772 KB Output is correct
4 Execution timed out 5031 ms 36020 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2692 KB Output is correct
4 Incorrect 4 ms 2688 KB Output isn't correct
5 Halted 0 ms 0 KB -