QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#718842 | #9605. 新生舞会 | zlt | 100 ✓ | 2507ms | 113736kb | C++14 | 4.8kb | 2024-11-06 21:36:14 | 2024-11-06 21:36:20 |
Judging History
answer
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
namespace IO {
char ibuf[1 << 17], *iS, *iT, obuf[1 << 17], *oS = obuf;
#define writesp(x) write(x), pc(' ')
#define writeln(x) write(x), pc('\n')
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, 1 << 17, stdin), (iS == iT ? EOF : *iS++) : *iS++)
template<typename T = int>
inline T read () {
char ch = gh();
T x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void flush () {
fwrite(obuf, 1, oS - obuf, stdout), oS = obuf;
}
inline void pc (char ch) {
if (oS == obuf + (1 << 17)) flush();
*oS++ = ch;
}
template<typename T>
inline void write (T x) {
static char stk[64], *tp = stk;
if (x < 0) {
x = ~(x - 1);
pc('-');
}
do {
*tp++ = x % 10;
x /= 10;
} while (x);
while (tp != stk) {
pc((*--tp) | 48);
}
}
}
using IO::read;
using IO::write;
using IO::pc;
using IO::flush;
struct i24 {
unsigned char a, b, c;
i24(int x = 0) {
a = x & 255;
b = (x >> 8) & 255;
c = (x >> 16) & 255;
}
inline int val() {
return a + ((int)b << 8) + ((int)c << 16);
}
};
const int maxn = 2000100;
int n, len;
i24 hd[maxn], to[maxn], nxt[maxn];
inline void add_edge(int u, int v) {
to[++len] = v;
nxt[len] = hd[u];
hd[u] = len;
}
namespace BIT {
int c[(1 << 21) + 50];
inline void update(int x, int d) {
for (int i = (++x); i < (1 << 21); i += (i & (-i))) {
c[i] += d;
}
}
inline void clear(int x) {
for (int i = (++x); i < (1 << 21); i += (i & (-i))) {
c[i] = 0;
}
}
inline int query(int x) {
int res = 0;
for (int i = (++x); i; i -= (i & (-i))) {
res += c[i];
}
return res;
}
inline int query(int l, int r) {
return query(r) - query(l - 1);
}
}
int top, tag, ans;
i24 stk[maxn], f[maxn], son[maxn], g[maxn], h[maxn];
bitset<maxn> vis;
inline int query(int x) {
int ans = 0, l = 0, r = (1 << 21) - 1;
for (int i = 20; ~i; --i) {
int mid = (l + r) >> 1;
if (x & (1 << i)) {
if (BIT::query(mid + 1, r) == r - mid) {
ans |= (1 << i);
r = mid;
} else {
l = mid + 1;
}
} else {
if (BIT::query(l, mid) == mid - l + 1) {
ans |= (1 << i);
l = mid + 1;
} else {
r = mid;
}
}
}
return ans;
}
inline void add(int x) {
if (!vis.test(x)) {
stk[++top] = x;
BIT::update(x, 1);
}
vis.set(x);
}
inline void clear() {
for (int i = 1; i <= top; ++i) {
BIT::clear(stk[i].val());
vis.reset(stk[i].val());
}
top = tag = 0;
}
int top_, stk_[maxn], it_[maxn], dfn[maxn], dfc, sz[maxn], rnk[maxn], p[maxn], fa[maxn];
inline void dfs_init() {
for (int i = 1; i <= n; ++i) {
it_[i] = hd[i].val();
}
}
inline void sim_dfs() {
dfs_init();
stk_[top_ = 1] = 1;
dfn[1] = dfc = 1;
rnk[1] = 1;
while (top_) {
int u = stk_[top_];
if (!it_[u]) {
--top_;
continue;
}
if (!vis.test(u)) {
vis.set(u);
stk_[++top_] = son[u].val();
dfn[son[u].val()] = ++dfc;
rnk[dfc] = son[u].val();
continue;
}
int _ = it_[u];
int v = to[_].val();
it_[u] = nxt[_].val();
if (v == son[u].val()) {
continue;
}
stk_[++top_] = v;
dfn[v] = ++dfc;
rnk[dfc] = v;
}
for (int i = 1; i <= n; ++i) {
vis.reset(i);
}
}
void solve() {
n = read();
len = 0;
for (int i = 1; i <= n; ++i) {
hd[i] = 0;
p[i] = 0;
}
for (int i = 2, p; i <= n; ++i) {
p = read();
add_edge(p, i);
fa[i] = p;
}
for (int u = n; u; --u) {
sz[u] = 1;
son[u] = 0;
for (int _ = hd[u].val(); _; _ = nxt[_].val()) {
int v = to[_].val();
sz[u] += sz[v];
if (sz[v] > sz[son[u].val()]) {
son[u] = v;
}
}
}
sim_dfs();
for (int _ = n; _; --_) {
int u = rnk[_];
tag ^= p[u];
p[u] ^= f[son[u].val()].val();
for (int _ = hd[u].val(); _; _ = nxt[_].val()) {
int v = to[_].val();
if (v == son[u].val()) {
continue;
}
int X = h[v].val() ^ p[u] ^ f[v].val() ^ tag;
for (int i = dfn[v]; i < dfn[v] + sz[v]; ++i) {
int w = rnk[i];
g[w] = g[w].val() ^ X;
add(g[w].val());
}
}
g[u] = p[u] ^ tag;
add(p[u] ^ tag);
f[u] = query(tag);
if (u != 1 && son[fa[u]].val() != u) {
p[fa[u]] ^= f[u].val();
h[u] = tag;
clear();
}
}
ans ^= f[1].val();
clear();
}
int main() {
int T = read();
while (T--) {
solve();
}
writeln(ans);
flush();
return 0;
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 7ms
memory: 69516kb
input:
12 13 1 2 1 4 2 5 3 3 2 9 6 4 392 1 2 2 4 4 3 3 6 9 10 9 11 13 14 15 15 17 18 19 20 6 21 23 12 24 26 27 28 29 30 31 32 33 31 34 33 36 9 38 40 41 25 42 44 45 46 47 48 49 50 51 52 53 21 32 52 54 58 59 60 53 61 63 64 65 66 67 68 69 70 4 1 71 74 75 76 77 78 79 80 81 52 82 55 84 86 84 87 89 90 91 92 93 1...
output:
1875
result:
ok 1 number(s): "1875"
Test #2:
score: 10
Accepted
time: 12ms
memory: 72928kb
input:
1 5000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 5 21 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 79 85 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...
output:
4950
result:
ok 1 number(s): "4950"
Test #3:
score: 10
Accepted
time: 11ms
memory: 70048kb
input:
1 5000 1 1 2 1 2 2 3 4 9 10 9 12 13 10 15 12 14 14 18 20 19 22 19 20 21 24 26 27 25 30 30 32 33 33 33 32 34 35 38 40 39 38 40 43 43 44 43 46 48 50 50 48 50 53 53 52 56 56 57 56 57 60 61 61 61 62 66 65 69 67 71 70 71 73 75 73 73 75 78 80 78 80 82 80 82 84 86 85 89 86 87 92 92 92 95 94 95 95 95 100 10...
output:
3204
result:
ok 1 number(s): "3204"
Subtask #2:
score: 10
Accepted
Test #4:
score: 10
Accepted
time: 2074ms
memory: 85028kb
input:
15 1 5 1 1 3 3 10603 1 2 2 1 5 3 6 3 2 7 6 6 10 5 4 16 4 16 18 4 11 22 8 14 2 26 22 9 10 20 28 26 1 27 8 35 3 4 6 25 14 9 33 44 15 26 28 34 24 18 48 5 33 11 37 32 19 14 41 6 46 60 8 25 62 32 59 27 54 50 62 44 51 18 53 46 42 31 26 11 78 71 40 60 2 13 35 84 34 76 51 88 33 13 88 85 80 70 21 74 54 79 75...
output:
11527
result:
ok 1 number(s): "11527"
Test #5:
score: 10
Accepted
time: 2507ms
memory: 105540kb
input:
1 2000000 1 1 1 4 5 5 3 6 4 1 11 2 11 4 15 11 11 11 1 16 11 15 22 6 7 23 4 5 8 2 27 1 5 3 15 30 30 21 34 28 22 24 25 33 45 13 1 46 27 27 39 15 42 44 38 27 52 39 27 58 36 37 29 34 30 44 29 55 17 60 34 30 61 29 61 13 12 67 70 9 67 40 54 72 14 80 42 27 49 88 12 2 53 8 57 93 74 22 22 85 61 79 89 55 23 1...
output:
16384
result:
ok 1 number(s): "16384"
Subtask #3:
score: 30
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 30
Accepted
time: 54ms
memory: 73152kb
input:
16 4 1 1 3 9 1 2 3 4 5 6 7 8 58 1 2 2 4 5 6 7 8 9 2 10 12 13 5 8 14 17 4 18 20 21 22 8 10 4 23 27 5 26 21 20 28 26 33 35 36 37 38 22 39 41 42 43 44 34 45 47 3 31 48 51 52 53 54 44 44 21 30 1 2 1 4 5 2 6 8 8 2 11 5 9 13 10 16 17 18 12 10 11 19 12 23 23 3 16 26 29 36 1 1 1 2 2 1 2 3 1 10 6 3 12 3 8 9 ...
output:
20841
result:
ok 1 number(s): "20841"
Test #7:
score: 30
Accepted
time: 60ms
memory: 74788kb
input:
1 200000 1 2 3 4 5 6 7 7 9 10 11 12 13 14 15 13 16 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 99 100...
output:
195053
result:
ok 1 number(s): "195053"
Test #8:
score: 30
Accepted
time: 35ms
memory: 72644kb
input:
1 200000 1 1 2 2 2 4 4 4 6 10 9 10 11 12 13 15 15 18 19 19 19 20 20 22 23 23 23 24 26 27 28 28 29 34 31 35 33 37 35 40 37 39 43 43 43 46 46 48 48 50 48 52 49 50 53 54 54 56 57 56 61 60 59 60 61 65 64 64 65 69 70 72 73 74 72 73 75 78 76 77 80 79 80 81 81 82 86 84 87 90 88 91 93 93 94 94 94 97 95 100 ...
output:
127754
result:
ok 1 number(s): "127754"
Test #9:
score: 30
Accepted
time: 41ms
memory: 74592kb
input:
1 200000 1 2 3 4 1 3 4 4 4 1 3 2 3 3 3 5 2 1 4 5 4 3 5 3 3 2 2 1 1 2 4 2 4 3 3 1 1 2 4 5 5 5 5 2 1 5 3 4 1 5 2 3 4 5 2 3 3 3 1 2 4 2 2 1 1 2 4 1 3 4 1 4 3 4 4 2 1 4 4 5 1 2 1 1 3 2 4 3 3 3 1 2 3 4 3 1 5 5 2 3 2 2 4 2 2 5 2 2 3 5 1 2 2 1 5 5 3 4 2 1 2 5 3 4 5 5 4 5 1 5 3 3 4 3 5 5 4 2 5 5 2 2 3 3 4 2...
output:
10
result:
ok 1 number(s): "10"
Test #10:
score: 30
Accepted
time: 44ms
memory: 76272kb
input:
1 200000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 ...
output:
66
result:
ok 1 number(s): "66"
Test #11:
score: 30
Accepted
time: 191ms
memory: 72668kb
input:
1 200000 1 2 2 1 5 3 2 7 4 1 5 10 2 3 15 16 13 1 12 13 19 13 19 16 23 9 10 1 23 26 30 7 25 16 25 36 16 27 10 39 40 20 6 5 30 3 46 41 35 30 24 28 28 8 38 25 32 38 29 21 56 17 24 38 5 7 62 58 13 8 11 45 47 55 55 12 64 8 55 7 5 31 73 20 85 83 44 74 58 65 57 66 27 47 66 56 90 39 96 15 37 14 30 61 96 73 ...
output:
8192
result:
ok 1 number(s): "8192"
Test #12:
score: 30
Accepted
time: 54ms
memory: 76872kb
input:
1 200000 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 25 62 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 99 100...
output:
199948
result:
ok 1 number(s): "199948"
Subtask #4:
score: 50
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #13:
score: 50
Accepted
time: 1510ms
memory: 105568kb
input:
13 397 1 2 3 1 4 4 6 2 8 10 11 12 13 5 14 16 17 18 19 20 17 21 7 23 25 26 18 16 22 11 27 18 28 32 35 36 17 37 39 40 28 17 41 23 44 16 13 13 46 50 51 16 16 52 55 56 21 57 59 38 28 9 18 60 65 22 66 68 69 70 71 72 73 9 74 76 77 78 79 80 81 25 82 84 25 85 87 88 51 89 91 87 92 94 95 42 96 98 59 99 101 10...
output:
523799
result:
ok 1 number(s): "523799"
Test #14:
score: 50
Accepted
time: 684ms
memory: 113736kb
input:
1 2000000 1 1 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 5 21 23 24 25 26 27 28 29 30 31 32 33 19 34 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 44 62 64 65 63 66 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 14 20 88 91 92 93 94 95 96 97 98 99 100...
output:
1949728
result:
ok 1 number(s): "1949728"
Test #15:
score: 50
Accepted
time: 469ms
memory: 107688kb
input:
1 2000000 1 2 1 4 3 4 5 6 6 10 11 8 9 10 11 13 16 15 18 16 19 19 22 20 23 23 24 28 28 30 29 28 30 33 33 35 33 34 37 36 37 39 41 42 41 44 44 47 45 47 50 49 49 52 53 52 54 55 56 60 60 60 60 62 64 63 64 68 66 67 70 70 71 72 73 74 76 74 79 79 78 82 80 80 83 86 84 86 85 87 88 90 91 93 94 93 94 95 96 97 9...
output:
1283040
result:
ok 1 number(s): "1283040"
Test #16:
score: 50
Accepted
time: 318ms
memory: 105548kb
input:
1 2000000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52...
output:
93
result:
ok 1 number(s): "93"
Test #17:
score: 50
Accepted
time: 1573ms
memory: 107648kb
input:
1 2000000 1 2 1 4 3 4 1 3 5 6 4 8 3 5 9 14 14 3 5 3 5 22 1 6 22 14 26 13 13 5 4 24 32 14 13 30 3 14 4 21 30 15 5 33 27 35 19 19 39 14 42 21 11 19 15 1 52 5 56 45 10 60 5 42 40 31 11 38 63 18 51 63 49 70 54 11 24 31 58 49 24 12 33 39 2 34 59 69 85 18 10 25 37 56 93 84 40 1 80 38 53 48 33 51 96 76 13 ...
output:
16384
result:
ok 1 number(s): "16384"
Test #18:
score: 50
Accepted
time: 292ms
memory: 105476kb
input:
1 2000000 1 1 3 4 5 1 4 1 2 3 1 1 2 5 4 5 5 3 5 3 3 1 2 5 5 4 2 4 5 1 4 1 3 4 5 2 3 2 5 1 5 3 2 4 4 4 1 4 2 4 3 2 5 3 5 1 4 3 2 4 4 1 3 4 3 4 3 5 5 1 4 1 4 5 5 1 2 3 1 3 3 5 2 5 4 5 2 5 3 4 3 1 4 4 3 3 2 5 1 5 1 4 2 2 5 3 4 1 4 4 4 5 1 3 4 4 5 1 5 4 2 1 2 3 4 1 3 4 2 4 1 3 1 5 4 4 3 5 2 2 1 1 5 3 4 ...
output:
8
result:
ok 1 number(s): "8"
Test #19:
score: 50
Accepted
time: 403ms
memory: 113716kb
input:
1 2000000 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 99 10...
output:
1999540
result:
ok 1 number(s): "1999540"
Test #20:
score: 50
Accepted
time: 1370ms
memory: 105632kb
input:
1 2000000 1 2 2 1 5 5 2 7 1 10 9 10 3 7 8 9 1 5 6 19 15 22 16 20 3 17 25 18 24 18 26 14 32 4 18 30 25 16 6 28 41 15 3 41 32 27 7 47 14 19 36 14 24 32 10 20 24 34 25 56 34 46 21 41 63 57 46 58 64 20 3 32 59 45 5 47 16 31 24 26 34 35 69 41 66 69 55 81 63 10 17 1 87 52 46 25 56 7 49 57 88 8 83 67 101 6...
output:
245760
result:
ok 1 number(s): "245760"