QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#129032 | #5445. Vulpecula | zhoukangyang | WA | 326ms | 45660kb | C++11 | 3.5kb | 2023-07-21 19:45:45 | 2023-07-21 19:45:45 |
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;
lb operator | (lb a, lb b) {
R(i, 63, 0) if(a[i]) b.insert(a[i]);
return b;
}
ull X[66], xo[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);
R(tp, 63, 0) L(o, 0, 1) {
ull W = o == 0 ? a.f[tp] : b.f[tp];
ull w = W;
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 = W;
L(i, 0, top - 1)
if((ids >> i & 1) && xo[i] == o)
w ^= X[i];
qwq.insert(w);
} else {
X[top] = W, xo[top] = o, ++top;
}
}
return qwq;
}
lb ans[N];
int dep[N];
vi e[N];
ull ANS[N];
vi fn[N];
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;
lb F;
while(cnt--) {
ull w=orz();
cin >> w;
F.insert(w);
}
dp[i].Fun.emplace_back(0, F);
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;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 32740kb
input:
2 1 2 2 3 2 1 1
output:
4 2
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 32796kb
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: 0ms
memory: 32748kb
input:
2 1 0 0
output:
0 0
result:
ok 2 lines
Test #4:
score: -100
Wrong Answer
time: 326ms
memory: 45660kb
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:
8779027715387561351 5216860202369640988 18394763710447274879 18385604738535651945 5207784842923561555 18446742668234539211 5216493656431066004 18446742668160117177 5216860202369580683 18385604738534448875 18446742668225074088 18446742015604218286 18276547845459911999 5244344978716907048 183573374989...
result:
wrong answer 1st lines differ - expected: '18434153946472599289', found: '8779027715387561351'