QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#102783#4909. 《关于因为与去年互测zjk撞题而不得不改题这回事》FISHER_0 1647ms409888kbC++142.6kb2023-05-03 17:43:412023-05-03 17:43:46

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 17:43:46]
  • 评测
  • 测评结果:0
  • 用时:1647ms
  • 内存:409888kb
  • [2023-05-03 17:43:41]
  • 提交

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, u);
	for (int v : g[u])
		if (v != fa && v != son[u]) dfs2(v, u, v);
}
pair<i64, int> mx[maxn + 5][20];
int lg2[maxn + 5];
inline int queryMx(int l, int r) {
	int t = lg2[r - l + 1];
	return max(mx[l][t], mx[r - (1 << t) + 1][t]).se;
}
struct seg {
	int l, r, id;
	bool operator<(const seg& b) const { return 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] = {a[rnk[i]], i};
		for (int j = 1; i + (1 << j) - 1 <= n; j++) mx[i][j] = max(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;
		for (int j = 61; ~j; j--) {
			int c = 0;
			for (i64 o : L)
				if (get(o, j)) c++;
			while (c < m) {
				i64 o = pop();
				if ((o & ans) != ans) 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: 5
Accepted
time: 1ms
memory: 40640kb

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:

1152921504606846976

result:

ok 1 number(s): "1152921504606846976"

Test #2:

score: 0
Accepted
time: 3ms
memory: 41048kb

input:

915
911 748
514 911
805 514
729 805
753 729
40 753
671 40
664 671
94 664
61 94
726 61
690 726
597 690
216 597
644 216
533 644
605 533
22 605
307 22
455 307
377 455
114 377
660 114
589 660
569 589
409 569
408 409
821 408
736 821
599 736
60 599
475 60
57 475
412 57
85 412
524 85
846 524
595 846
262 59...

output:

288230376151711752

result:

ok 1 number(s): "288230376151711752"

Test #3:

score: -5
Wrong Answer
time: 1ms
memory: 41404kb

input:

930
111 896
637 111
559 637
289 559
103 289
759 103
341 759
605 341
778 605
154 778
169 154
721 169
631 721
741 631
750 741
344 750
641 344
639 641
769 639
48 769
389 48
25 389
70 25
508 70
185 508
199 185
602 199
89 602
473 89
565 473
373 565
865 373
867 865
658 867
271 658
685 271
269 685
317 269
...

output:

1152921504606846976

result:

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

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #17:

score: 0
Wrong Answer
time: 67ms
memory: 95108kb

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:

4096

result:

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

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: 1647ms
memory: 409888kb

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:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
4096
0
0
0
0
4096
0
0
0
0
0
0
0
0
0
4
0
0
0
0
4
131104
0
0
0
4
2
0
258
0
0
0
0
131072
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4096
2
0
0
0
0
0
512
0
4
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
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 1st numbers differ - expected: '4', found: '0'

Subtask #8:

score: 0
Skipped

Dependency #1:

0%