QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#128995 | #5445. Vulpecula | zhoukangyang | TL | 980ms | 69540kb | C++11 | 3.5kb | 2023-07-21 18:36:02 | 2023-07-21 18:36:04 |
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];
lb operator & (lb a, lb b) {
int ma = a.mxp(), mb = b.mxp();
if(ma > mb) swap(a, b), swap(ma, mb);
if(ma == -1) return a;
if(ma != mb) return b[mb] = 0, a & b;
ull xay = a[ma] ^ b[mb], sw = a[ma];
a[ma] = b[mb] = 0;
auto ns = a & b;
int pn = 0;
R(i, 63, 0) if(a[i]) X[++pn] = a[i];
R[pn + 1] = b;
R(i, pn, 1)
R[i] = R[i + 1], R[i].insert(X[i]);
if(!R[1].check(xay)) return ns;
L(i, 1, pn) if(!R[i + 1].check(xay)) xay ^= X[i], sw ^= X[i];
ns[ma] = sw;
return ns;
}
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);
}
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
L(i, 2, n) {
cin >> fa[i];
e[fa[i]].emplace_back(i);
e[i].emplace_back(fa[i]);
}
L(i, 1, n) {
int cnt;
cin >> cnt;
while(cnt--) {
ull w;
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);
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);
cout << ans << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 11ms
memory: 57728kb
input:
2 1 2 2 3 2 1 1
output:
4 2
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 10ms
memory: 57744kb
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: 5ms
memory: 57796kb
input:
2 1 0 0
output:
0 0
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 980ms
memory: 69540kb
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: -100
Time Limit Exceeded
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...