QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#129031 | #5445. Vulpecula | zhoukangyang | ML | 2370ms | 225064kb | C++11 | 3.7kb | 2023-07-21 19:39:26 | 2023-07-21 19:39:27 |
Judging History
answer
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector < int >
#define sz(a) ((int) (a).size())
#define ll long long
#define ull unsigned long long
#define me(a, x) memset(a, x, sizeof(a))
using namespace std;
const int N = 5e4 + 7;
struct lb {
ull f[64];
lb() {
me(f, 0);
}
ull & operator [] (int x) {
return f[x];
}
void insert (ull x) {
R(i, 63, 0) if(x >> i & 1) {
if(!f[i]) f[i] = x;
x ^= f[i];
}
}
bool check(ull x) {
R(i, 63, 0) if(x >> i & 1) {
if(!f[i]) return false;
x ^= f[i];
}
return true;
}
void clear () {
me(f, 0);
}
int size () {
int cnt = 0;
L(i, 0, 63) if(f[i]) cnt += 1;
return cnt;
}
int mxp () {
R(i, 63, 0) if(f[i]) return i;
return -1;
}
ull mxv() {
ull ret = 0;
R(i, 63, 0) if((ret ^ f[i]) > ret) ret ^= f[i];
return ret;
}
} pre[100], now, F[N];
lb operator | (lb a, lb b) {
R(i, 63, 0) if(a[i]) b.insert(a[i]);
return b;
}
ull X[66];
lb R[66];
ull iF[64], ID[64];
lb operator & (const lb &a, const lb &b) {
lb qwq;
int top = 0;
me(iF, 0), me(ID, 0);
L(i, 0, 63) iF[i] = a.f[i];
R(t, 63, 0) if(b.f[t]) {
ull w = b.f[t];
ull ids = 1ull << top;
R(i, 63, 0) if(w >> i & 1) {
if(!iF[i]) {
iF[i] = w, ID[i] = ids;
}
w ^= iF[i];
ids ^= ID[i];
}
if(ids) {
w = b.f[t];
L(i, 0, top - 1)
if(ids >> i & 1)
w ^= X[i];
qwq.insert(w);
} else {
X[top] = b.f[t], ++top;
}
}
return qwq;
}
lb ans[N];
int dep[N];
vi e[N];
ull ANS[N];
vi fn[N];
void dfs(int x, int f) {
fn[dep[x]].emplace_back(x);
for(auto v : e[x]) if(v != f) {
dep[v] = dep[x] + 1, ans[v] = ans[x] & F[v], dfs(v, x);
}
}
struct Depu {
vector < pair < int, lb > > Fun;
void reduce() {
int p = 0;
L(i, 0, sz(Fun) - 1) {
if(!i || Fun[i].second.size() != Fun[i - 1].second.size()) {
swap(Fun[p], Fun[i]);
++p;
}
}
if(p != sz(Fun)) {
Fun.resize(p);
}
}
friend Depu operator & (Depu u, Depu v) {
int x = 0, y = 0;
Depu ans;
while(x < sz(u.Fun) && y < sz(v.Fun)) {
if(u.Fun[x].first <= v.Fun[y].first) {
ans.Fun.emplace_back(u.Fun[x].first,
y > 0 ? u.Fun[x].second & v.Fun[y - 1].second :
u.Fun[x].second);
++x;
} else {
ans.Fun.emplace_back(v.Fun[y].first,
x > 0 ? u.Fun[x - 1].second & v.Fun[y].second :
v.Fun[y].second);
++y;
}
}
ans.reduce();
return ans;
}
Depu shift(int k) {
Depu qwq = (*this);
for(auto&u : qwq.Fun)
u.first += k;
return qwq;
}
};
Depu dp[N];
int n, fa[N];
void dfs1(int x, int fa) {
for(auto &v : e[x]) if(v != fa) {
dfs1(v, x), dp[x] = dp[x] & dp[v].shift(1);
}
}
void dfs2(int x, int fa) {
for(auto &v : e[x]) if(v != fa) {
dp[v] = dp[v] & dp[x].shift(1), dfs2(v, x);
}
}
mt19937_64 orz;
int main() {
// freopen("tree.in", "r", stdin);
// freopen("tree.out", "w", stdout);
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
n = 100;
cin >> n;
L(i, 2, n) {
fa[i] = i - 1;
cin >> fa[i];
e[fa[i]].emplace_back(i);
e[i].emplace_back(fa[i]);
}
L(i, 1, n) {
int cnt;
cnt=63;
cin >> cnt;
while(cnt--) {
ull w=orz();
cin >> w;
F[i].insert(w);
}
dp[i].Fun.emplace_back(0, F[i]);
dp[i].Fun.emplace_back(n, lb());
}
dfs1(1, 0);
dfs2(1, 0);
ull sim = 0;
L(i, 1, n) {
ull ans = 0;
L(j, 0, sz(dp[i].Fun) - 2)
ans += dp[i].Fun[j].second.mxv() * (dp[i].Fun[j + 1].first - dp[i].Fun[j].first);
// sim += ans;
cout << ans << '\n';
}
// cout << sim << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 9ms
memory: 57672kb
input:
2 1 2 2 3 2 1 1
output:
4 2
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 57904kb
input:
5 1 2 2 3 3 83 75 58 4 125 124 58 16 4 39 125 71 112 3 69 66 5 4 48 73 69 6
output:
171 125 183 142 243
result:
ok 5 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 57688kb
input:
2 1 0 0
output:
0 0
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 102ms
memory: 69408kb
input:
500 1 2 3 2 1 2 6 2 4 6 6 10 7 12 7 9 8 10 12 20 12 19 15 24 25 23 25 22 29 29 28 26 31 25 34 31 35 33 39 37 36 42 37 37 41 43 42 46 45 45 49 52 53 50 46 50 49 52 58 57 57 61 57 59 56 65 63 59 66 65 63 70 70 68 72 71 73 72 72 76 72 75 80 76 76 82 83 80 89 89 91 85 85 90 89 89 89 92 93 91 92 93 98 96...
output:
18434153946472599289 17931933346714042066 17916198204903720383 17916198204176061148 17931933346710961779 18445169471807930489 17931926407666058065 18445169471807930348 17931933346714042064 17916198204176061019 18445169471807930488 18446738828973977865 17916198204176061018 17931926407666058064 184467...
result:
ok 500 lines
Test #5:
score: 0
Accepted
time: 1836ms
memory: 191116kb
input:
49999 1 1 3 1 1 5 2 4 1 8 7 6 3 13 4 12 12 1 19 8 2 16 23 6 21 3 11 1 21 7 14 6 3 28 31 24 6 22 27 11 17 25 41 5 17 13 1 48 17 14 31 18 43 30 53 27 7 39 4 2 11 55 48 17 32 15 24 44 53 63 70 31 21 17 74 37 34 48 15 33 14 53 8 9 72 10 65 77 69 36 32 61 51 63 77 25 71 47 59 94 39 41 77 24 5 33 43 18 72...
output:
18446744063446965319 18316893942693974299 18446744073709548919 18355577725686532847 18446744073709551614 18446744073709551615 18446744073709551614 18446744073709551615 18446736549671322125 12348860911474380074 18446744072601433415 18446744073709551615 17335313836902106838 18446744073709551576 184467...
result:
ok 49999 lines
Test #6:
score: 0
Accepted
time: 2370ms
memory: 225064kb
input:
50000 1 1 1 2 2 2 3 4 4 5 5 5 6 6 8 8 8 8 8 8 9 9 10 10 11 11 12 12 13 13 13 14 14 14 15 15 15 16 18 18 19 19 20 20 20 20 21 23 24 24 24 24 26 26 27 27 28 29 29 29 30 30 30 31 31 32 32 32 32 33 33 33 34 34 35 35 36 36 36 36 37 38 38 38 38 39 39 39 40 41 42 43 44 44 45 45 45 46 46 47 47 47 47 47 48 4...
output:
17388026687988753207 18446123107769912009 18433598785516292263 18446483694069646475 18446744073700722557 18446743950305151556 18446123107769912008 18446170606667738311 18446744071353497819 18446744065870877991 18446744073709531050 18446744073709231216 18446546425974411728 18446744073709533965 184467...
result:
ok 50000 lines
Test #7:
score: -100
Memory Limit Exceeded
input:
50000 1 1 3 4 5 6 5 7 3 10 6 12 12 12 5 8 17 4 19 20 17 22 22 22 25 25 27 27 28 22 31 31 31 34 34 35 37 38 38 40 41 42 43 42 44 46 40 42 47 50 50 40 53 41 42 56 57 58 59 59 61 62 59 64 65 65 59 61 69 62 71 72 73 72 72 74 58 62 79 80 79 82 74 84 84 84 46 72 89 90 90 34 93 94 94 96 94 95 95 100 101 10...