QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#48739#4387. Static Query on Treeneko_nyaa#AC ✓194ms53160kbC++144.0kb2022-09-15 14:20:062022-09-15 14:20:07

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-15 14:20:07]
  • 评测
  • 测评结果:AC
  • 用时:194ms
  • 内存:53160kb
  • [2022-09-15 14:20:06]
  • 提交

answer

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<class T>
struct RMQ {
	vector<vector<T>> jmp;
	RMQ(const vector<T>& V) : jmp(1, V) {
		for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
			jmp.emplace_back(sz(V) - pw * 2 + 1);
			rep(j,0,sz(jmp[k]))
				jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
		}
	}
	T query(int a, int b) {
		assert(a < b); // or return inf if a == b
		int dep = 31 - __builtin_clz(b - a);
		return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
	}
};

struct LCA {
	int T = 0;
	vi time, path, ret, depth;
	RMQ<int> rmq;

	LCA(vector<vi>& C) : time(sz(C)), depth(sz(C)),  rmq((dfs(C,0,-1), ret)) {}
	void dfs(vector<vi>& C, int v, int par) {
		time[v] = T++; 
		if (par != -1) depth[v] = depth[par] + 1;
		for (int y : C[v]) if (y != par) {
			path.push_back(v), ret.push_back(time[v]);
			dfs(C, y, v);
		}
	}

	int lca(int a, int b) {
		if (a == b) return a;
		tie(a, b) = minmax(time[a], time[b]);
		return path[rmq.query(a, b)];
	}

	int dist(int a, int b) {
		return depth[a] + depth[b] - 2*depth[lca(a,b)];
	}
};

typedef vector<pair<int, int>> vpi;
vpi compressTree(LCA& lca, const vi& subset) {
	static vi rev; rev.resize(sz(lca.time));
	vi li = subset, &T = lca.time;
	auto cmp = [&](int a, int b) { return T[a] < T[b]; };
	sort(all(li), cmp);
	int m = sz(li)-1;
	rep(i,0,m) {
		int a = li[i], b = li[i+1];
		li.push_back(lca.lca(a, b));
	}
	sort(all(li), cmp);
	li.erase(unique(all(li)), li.end());
	rep(i,0,sz(li)) rev[li[i]] = i;
	vpi ret = {pii(0, li[0])};
	rep(i,0,sz(li)-1) {
		int a = li[i], b = li[i+1];
		ret.emplace_back(rev[lca.lca(a, b)], b);
	}
	return ret;
}

const int MAXN = 200005;

vector<int> adj[MAXN];
int isA[MAXN], isB[MAXN], isC[MAXN];
int hasA[MAXN], hasB[MAXN], hasC[MAXN];

void dfs(int now, int prv, int foundC) {
	hasC[now] = foundC;
	hasA[now] = isA[now];
	hasB[now] = isB[now];

	for (int u: adj[now]) {
		if (u != prv) {
			dfs(u, now, foundC | isC[u]);
			hasA[now] |= hasA[u];
			hasB[now] |= hasB[u];
		}
	}
}

void solve() {
	int n, q; cin >> n >> q;
	vector<vi> ed(n);
	for (int i = 2; i <= n; i++) {
		int p; cin >> p;
		ed[p-1].push_back(i-1);
		ed[i-1].push_back(p-1);
	}

	LCA lca(ed);

	while (q--) {
		set<int> A, B, C;
		vector<int> nodes;

		int as, bs, cs; cin >> as >> bs >> cs;
		for (int i = 0; i < as; i++) {
			int x; cin >> x; x--;
			nodes.push_back(x);
			A.insert(x);
		}
		for (int i = 0; i < bs; i++) {
			int x; cin >> x; x--;
			nodes.push_back(x);
			B.insert(x);
		}
		for (int i = 0; i < cs; i++) {
			int x; cin >> x; x--;
			nodes.push_back(x);
			C.insert(x);
		}

		vpi nw = compressTree(lca, nodes);
		for (int i = 0; i < nw.size(); i++) {
			adj[i].clear();

			int id = nw[i].second;
			if (A.count(id)) isA[i] = 1;
			if (B.count(id)) isB[i] = 1;
			if (C.count(id)) isC[i] = 1;
		}

		for (int i = 1; i < nw.size(); i++) {
			int u = nw[i].first; int v = i;
			adj[u].push_back(v);
			adj[v].push_back(u);
		}

		dfs(0, 0, isC[0]);

		int ans = 0;
		for (int i = 0; i < nw.size(); i++) {
			if (hasA[i] && hasB[i] && hasC[i]) {
				ans++;
				//cout << "NODE " << nw[i].second+1 << '\n';
			}
		}
		for (int i = 1; i < nw.size(); i++) {
			int u = nw[i].first; int v = i; // u is the parent
			if (hasA[u] && hasB[u] && hasC[u] && hasA[v] && hasB[v] && hasC[v]) {
				// all nodes from u to v eligible
				ans += lca.dist(nw[i].second, nw[u].second) - 1;

				//cout << "PATH " << nw[i].second+1 << ' ' << nw[u].second+1 << '\n';
			}
		}
		cout << ans << '\n';

		for (int i = 0; i < nw.size(); i++) {
			hasA[i] = isA[i] = 0;
			hasB[i] = isB[i] = 0;
			hasC[i] = isC[i] = 0;
		}
	}
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int t; cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 194ms
memory: 53160kb

input:

1
200000 18309
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...

output:

102147
62590
87270
88880
7654
61542
62953
85022
55135
54125
70500
64356
25824
88300
42278
15336
18132
28734
90282
42889
28099
31311
96842
19959
34366
60205
78358
91142
56048
74688
86091
51979
94750
11989
89544
86860
56720
29534
52343
90031
79002
90293
94554
48340
65015
9181
15016
19884
49445
14181
6...

result:

ok 18309 numbers