QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#102930#4909. 《关于因为与去年互测zjk撞题而不得不改题这回事》FISHER_0 1808ms176348kbC++142.7kb2023-05-03 20:17:212023-05-03 20:17:25

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-03 20:17:25]
  • 评测
  • 测评结果:0
  • 用时:1808ms
  • 内存:176348kb
  • [2023-05-03 20:17:21]
  • 提交

answer

#include <bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define EB emplace_back
using namespace std;
typedef long long i64;
const int maxn = 1000000;
vector<int> g[maxn + 5];
i64 a[maxn + 5];
int dep[maxn + 5];
int siz[maxn + 5];
int son[maxn + 5];
int f[maxn + 5];
void dfs1(int u, int fa) {
	f[u] = fa;
	dep[u] = dep[fa] + 1;
	siz[u] = 1;
	for (int v : g[u]) {
		if (v == fa) continue;
		dfs1(v, u);
		siz[u] += siz[v];
		if (siz[v] > siz[son[u]]) son[u] = v;
	}
}
int tp[maxn + 5];
int id[maxn + 5], rnk[maxn + 5], stamp;
void dfs2(int u, int fa, int t) {
	tp[u] = t;
	rnk[id[u] = ++stamp] = u;
	if (son[u]) dfs2(son[u], u, t);
	for (int v : g[u])
		if (v != fa && v != son[u]) dfs2(v, u, v);
}
int mx[maxn + 5][20];
int lg2[maxn + 5];
inline int mxid(int x, int y) { return a[rnk[x]] > a[rnk[y]] ? x : y; }
inline int queryMx(int l, int r) {
	int t = lg2[r - l + 1];
	return mxid(mx[l][t], mx[r - (1 << t) + 1][t]);
}
struct seg {
	int l, r, id;
	bool operator<(const seg& b) const { return a[rnk[id]] == a[rnk[b.id]] ? id < b.id : a[rnk[id]] < a[rnk[b.id]]; }
};
set<seg> s;
inline void ins(int l, int r) { s.insert({l, r, queryMx(l, r)}); }
void init(int x, int y) {
	while (tp[x] != tp[y]) {
		if (dep[tp[x]] < dep[tp[y]]) swap(x, y);
		ins(id[tp[x]], id[x]);
		x = f[tp[x]];
	}
	if (dep[x] < dep[y]) swap(x, y);
	ins(id[y], id[x]);
}
i64 pop() {
	if (s.empty()) return 0;
	seg nw = *s.begin();
	s.erase(nw);
	if (nw.l < nw.id) ins(nw.l, nw.id - 1);
	if (nw.id < nw.r) ins(nw.id + 1, nw.r);
	return a[rnk[nw.id]];
}
inline bool get(i64 v, int w) { return (v >> w) & 1; }
int main() {
	int n, q;
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		g[u].PB(v), g[v].PB(u);
	}
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	dfs1(1, 0), dfs2(1, 0, 1);
	for (int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1;
	for (int i = n; i; i--) {
		mx[i][0] = i;
		for (int j = 1; i + (1 << j) - 1 <= n; j++) mx[i][j] = mxid(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
	}
	scanf("%d", &q);
	i64 ans = 0;
	for (int i = 1; i <= q; i++) {
		int x, y, m;
		scanf("%d%d%d", &x, &y, &m);
		x = (x ^ ans) % n + 1, y = (y ^ ans) % n + 1;
		init(x, y);
		vector<i64> L;
		ans = 0;
		bool ed = 0;
		for (int j = 61; ~j; j--) {
			int c = 0;
			for (i64 o : L) c += get(o, j);
			while (c < m && !ed) {
				i64 o = pop();
				if ((o & ans) != ans) { ed = 1; break; }
				L.PB(o);
				if (get(o, j)) c++;
				else break;
			}
			if (c >= m) {
				vector<i64> nL; 
				for (i64 o : L)
					if (get(o, j)) nL.PB(o);
				L.swap(nL);
				ans |= 1LL << j;
			}
		}
		printf("%lld\n", ans);
		s.clear();
	}
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 41296kb

input:

931
184 700
485 184
419 485
386 419
308 386
114 308
301 114
598 301
120 598
144 120
595 144
812 595
236 812
7 236
543 7
327 543
858 327
68 858
177 68
398 177
899 398
408 899
848 408
202 848
269 202
304 269
540 304
647 540
672 647
314 672
157 314
241 157
745 241
300 745
343 300
92 343
117 92
30 117
2...

output:

4096

result:

wrong answer 1st numbers differ - expected: '1152921504606846976', found: '4096'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #17:

score: 0
Wrong Answer
time: 82ms
memory: 69460kb

input:

99115
98506 98914
1961 98506
45808 1961
23027 45808
16655 23027
66393 16655
77250 66393
68284 77250
53684 68284
21189 53684
84955 21189
73464 84955
47574 73464
40651 47574
21101 40651
6589 21101
59680 6589
6185 59680
25529 6185
207 25529
33286 207
98459 33286
92565 98459
85446 92565
97388 85446
1630...

output:

2

result:

wrong answer 1st numbers differ - expected: '2050', found: '2'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Wrong Answer

Test #45:

score: 0
Wrong Answer
time: 1808ms
memory: 176348kb

input:

996678
2 1
3 1
4 1
5 1
6 3
7 5
8 5
9 5
10 7
11 8
12 9
13 1
14 2
15 7
16 4
17 5
18 17
19 16
20 2
21 1
22 1
23 9
24 17
25 19
26 10
27 9
28 7
29 25
30 25
31 4
32 11
33 31
34 21
35 13
36 19
37 25
38 10
39 11
40 20
41 35
42 1
43 19
44 20
45 41
46 1
47 19
48 5
49 28
50 21
51 33
52 7
53 14
54 21
55 20
56 1...

output:

4
0
4
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
8
0
0
0
0
16
0
0
4096
0
0
0
0
4096
0
0
0
0
2
0
0
0
0
4
0
0
0
0
32
64
0
0
0
512
64
4
4096
0
2
0
0
131072
0
0
0
0
0
0
0
0
2
0
0
0
2
0
4096
2
0
0
0
0
0
512
2
8
0
0
4096
64
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
512
0
0
36
0
0
0
0
0
0
0
64
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

wrong answer 6382nd numbers differ - expected: '17592186044416', found: '64'

Subtask #8:

score: 0
Skipped

Dependency #1:

0%