QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#102358 | #4909. 《关于因为与去年互测zjk撞题而不得不改题这回事》 | FISHER_ | 10 | 106ms | 118112kb | C++14 | 3.2kb | 2023-05-03 09:51:33 | 2023-05-03 09:51:38 |
Judging History
answer
#include <bits/stdc++.h>
#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 anc[maxn + 5][20];
void dfs1(int u, int fa) {
dep[u] = dep[fa] + 1;
anc[u][0] = fa;
for (int i = 1; (1 << i) < dep[u]; i++) anc[u][i] = anc[anc[u][i - 1]][i - 1];
for (int v : g[u])
if (v != fa) dfs1(v, u);
}
inline int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = 19; ~i; i--)
if (dep[anc[x][i]] >= dep[y]) x = anc[x][i];
if (x == y) return x;
for (int i = 19; ~i; i--)
if (anc[x][i] != anc[y][i]) x = anc[x][i], y = anc[y][i];
return anc[x][0];
}
int nxt[65 * maxn + 5][2], siz[65 * maxn + 5];
int pcnt;
inline bool get(i64 v, int w) { return (v >> w) & 1; }
void insert(int& x, int op, i64 v) {
x = ++pcnt;
int p = x;
for (int i = 61; ~i; i--) {
int c = get(v, i);
nxt[p][!c] = nxt[op][!c], nxt[p][c] = ++pcnt;
siz[p] = siz[op] + 1;
p = nxt[p][c], op = nxt[op][c];
}
siz[p] = siz[op] + 1;
}
int merge(int x, int y, int w = 61) {
if (!x || !y) return x | y;
int p = ++pcnt;
if (w < 0) {
siz[p] = siz[x] + siz[y];
return p;
}
siz[p] = siz[x] + siz[y];
nxt[p][0] = merge(nxt[x][0], nxt[y][0], w - 1);
nxt[p][1] = merge(nxt[x][1], nxt[y][1], w - 1);
return p;
}
int build(int p1, int p2, int p3, int p4, int p5, int w) {
int p = ++pcnt;
siz[p] = siz[p1] + siz[p2] - siz[p3] - siz[p4] + siz[p5];
if (w < 0) return p;
if (siz[nxt[p1][0]] + siz[nxt[p2][0]] - siz[nxt[p3][0]] - siz[nxt[p4][0]] + siz[nxt[p5][0]])
nxt[p][0] = build(nxt[p1][0], nxt[p2][0], nxt[p3][0], nxt[p4][0], nxt[p5][0], w - 1);
if (siz[nxt[p1][1]] + siz[nxt[p2][1]] - siz[nxt[p3][1]] - siz[nxt[p4][1]] + siz[nxt[p5][1]])
nxt[p][1] = build(nxt[p1][1], nxt[p2][1], nxt[p3][1], nxt[p4][1], nxt[p5][1], w - 1);
return p;
}
int rt[maxn + 5];
void dfs2(int u, int fa) {
insert(rt[u], rt[fa], a[u]);
for (int v : g[u])
if (v != fa) dfs2(v, u);
}
i64 query(int p1, int p2, int p3, int p4, int p5, int m, i64 v = 0, int w = 61) {
if (w < 0) return v;
if (siz[nxt[p1][1]] + siz[nxt[p2][1]] - siz[nxt[p3][1]] - siz[nxt[p4][1]] + siz[nxt[p5][1]] >= m)
return query(nxt[p1][1], nxt[p2][1], nxt[p3][1], nxt[p4][1], nxt[p5][1], m, v | (1 << w), w - 1);
int mg = build(nxt[p1][1], nxt[p2][1], nxt[p3][1], nxt[p4][1], nxt[p5][1], w - 1);
return query(nxt[p1][0], nxt[p2][0], nxt[p3][0], nxt[p4][0], merge(nxt[p5][0], mg, w - 1), m, 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);
int bak = pcnt;
scanf("%d", &q);
i64 lstans = 0;
for (int i = 1; i <= q; i++) {
int x, y, m;
scanf("%d%d%d", &x, &y, &m);
x = (x ^ lstans) % n + 1, y = (y ^ lstans) % n + 1;
int z1 = lca(x, y), z2 = anc[z1][0];
if (dep[x] + dep[y] - 2 * dep[z1] + 1 < m) puts("0"), lstans = 0;
else printf("%lld\n", lstans = query(rt[x], rt[y], rt[z1], rt[z2], 0, m));
while (pcnt > bak) nxt[pcnt][0] = nxt[pcnt][1] = 0, pcnt--;
}
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 28108kb
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:
268435456
result:
wrong answer 1st numbers differ - expected: '1152921504606846976', found: '268435456'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 10
Accepted
Test #17:
score: 10
Accepted
time: 98ms
memory: 116392kb
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:
2050
result:
ok 1 number(s): "2050"
Test #18:
score: 0
Accepted
time: 99ms
memory: 116832kb
input:
99546 79711 12863 50539 79711 13393 50539 27933 13393 13465 27933 79157 13465 53742 79157 51081 53742 32220 51081 21079 32220 85595 21079 50222 85595 14565 50222 4589 14565 13763 4589 58913 13763 93835 58913 34953 93835 2185 34953 10246 2185 64420 10246 44274 64420 63093 44274 8007 63093 85947 8007 ...
output:
512
result:
ok 1 number(s): "512"
Test #19:
score: 0
Accepted
time: 84ms
memory: 118112kb
input:
99762 90013 76047 42293 90013 7801 42293 75274 7801 59320 75274 60896 59320 10435 60896 5384 10435 34648 5384 15596 34648 92041 15596 67457 92041 20760 67457 65611 20760 81462 65611 38984 81462 17583 38984 83787 17583 59980 83787 71477 59980 31143 71477 92168 31143 71205 92168 69348 71205 6111 69348...
output:
16386
result:
ok 1 number(s): "16386"
Test #20:
score: 0
Accepted
time: 106ms
memory: 116432kb
input:
99132 46469 40521 51811 46469 47968 51811 10584 47968 73 10584 27351 73 16693 27351 12495 16693 53425 12495 95973 53425 24901 95973 82771 24901 49155 82771 35995 49155 50432 35995 91209 50432 5781 91209 83457 5781 41361 83457 37973 41361 48829 37973 62896 48829 77593 62896 21307 77593 86547 21307 61...
output:
8194
result:
ok 1 number(s): "8194"
Test #21:
score: 0
Accepted
time: 94ms
memory: 116248kb
input:
99403 81802 91324 60321 81802 76749 60321 70097 76749 16085 70097 8301 16085 61886 8301 72994 61886 23906 72994 18815 23906 6781 18815 7774 6781 18318 7774 54769 18318 39330 54769 55677 39330 46758 55677 36164 46758 10159 36164 24678 10159 29603 24678 14941 29603 7966 14941 42934 7966 35909 42934 24...
output:
32770
result:
ok 1 number(s): "32770"
Test #22:
score: 0
Accepted
time: 95ms
memory: 117260kb
input:
99468 33859 68644 12306 33859 44304 12306 18200 44304 27325 18200 35907 27325 88149 35907 71599 88149 86384 71599 83793 86384 19513 83793 4843 19513 3007 4843 52878 3007 83019 52878 5275 83019 61517 5275 21453 61517 55993 21453 50710 55993 16211 50710 76061 16211 12048 76061 41970 12048 86181 41970 ...
output:
514
result:
ok 1 number(s): "514"
Test #23:
score: 0
Accepted
time: 73ms
memory: 115796kb
input:
99179 45430 91876 8718 45430 75718 8718 15306 75718 21806 15306 78221 21806 74287 78221 66218 74287 66830 66218 64948 66830 16118 64948 33879 16118 81821 33879 69640 81821 27802 69640 25979 27802 6393 25979 63447 6393 48459 63447 53612 48459 27525 53612 52654 27525 80810 52654 767 80810 23808 767 82...
output:
32768
result:
ok 1 number(s): "32768"
Test #24:
score: 0
Accepted
time: 98ms
memory: 115924kb
input:
99240 8561 98467 49571 8561 13264 49571 94195 13264 85879 94195 53012 85879 29828 53012 25813 29828 57793 25813 10678 57793 88525 10678 70070 88525 54163 70070 51466 54163 3857 51466 77958 3857 29023 77958 154 29023 5173 154 4349 5173 24310 4349 21821 24310 36125 21821 75498 36125 7147 75498 22336 7...
output:
32770
result:
ok 1 number(s): "32770"
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
Memory Limit Exceeded
Test #45:
score: 0
Memory Limit Exceeded
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:
result:
Subtask #8:
score: 0
Skipped
Dependency #1:
0%