QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #287354 | #5445. Vulpecula | ushg8877 | TL | 4ms | 43008kb | C++14 | 1.9kb | 2023-12-20 13:24:28 | 2023-12-20 13:24:29 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=5e4+5;
const int B=64;
int n;
vector<int> son[MAXN];
struct Linear_Basis{
ll a[B];int p[B],op;
Linear_Basis(){memset(a,0,sizeof(a));memset(p,0,sizeof(p));}
void insert(ll x,int t){
for(int i=(op?0:B-1);(op?i<B:i>=0);(op?i++:i--)) if(x>>i&1){
if(!a[i]){a[i]=x;p[i]=t;return;}
else if(p[i]>t) swap(a[i],x),swap(p[i],t);
x^=a[i];
}
}
ll ask(){
ll x=0;
for(int i=B-1;i>=0;i--) if(~x>>i&1) x^=a[i];
return x;
}
}L[MAXN];
Linear_Basis orthogonal(Linear_Basis A,int t=1e9){// 求正交，正交集关键位为 lowbit!
Linear_Basis X;X.op=A.op^1;
for(int i=0;i<B;i++) if(A.p[i]>t) A.a[i]=A.p[i]=0;
for(int i=A.op?0:B-1;A.op?i<B:i>=0;A.op?i++:i--) if(A.a[i]) {
for(int j=A.op?i-1:i+1;A.op?j>=0:j<B;A.op?j--:j++) if(A.a[j]>>i&1) A.a[j]^=A.a[i];
} // 高斯消元
for(int i=A.op?0:B-1;A.op?i<B:i>=0;A.op?i++:i--) if(!A.a[i]){
X.a[i]=(1ull<<i);
for(int j=A.op?i-1:i+1;A.op?j>=0:j<B;A.op?j--:j++) if(A.a[j]>>i&1) X.a[i]|=(1ull<<j);
}
return X;
}
void dfs(int u){
for(int v:son[u]){
dfs(v);
for(int i=0;i<B;i++) if(L[v].a[i])
L[u].insert(L[v].a[i],L[v].p[i]+1);
}
}
void dfs1(int u){
for(int v:son[u]){
for(int i=0;i<B;i++) if(L[u].a[i])
L[v].insert(L[u].a[i],L[u].p[i]+1);
dfs1(v);
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=2,f;i<=n;i++) cin>>f,son[f].push_back(i);
for(int i=1;i<=n;i++){
int m,x;cin>>m;
while(m--){
cin>>x;
L[i].insert(x,0);
}
}
for(int i=1;i<=n;i++) L[i]=orthogonal(L[i]);
dfs(1);
dfs1(1);
for(int i=1;i<=n;i++){
vector<int> a;
for(int j=0;j<B;j++) if(L[i].a[j]) a.push_back(L[i].p[j]);
a.push_back(n);a.push_back(0);
sort(a.begin(),a.end());
ll ans=0;
for(int j=0;j<a.size()-1;j++)
ans+=(a[j+1]-a[j])*orthogonal(L[i],a[j]).ask();
cout<<ans<<endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 43008kb
input:
2 1 2 2 3 2 1 1
output:
4 2
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 42724kb
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: 3ms
memory: 42692kb
input:
2 1 0 0
output:
0 0
result:
ok 2 lines
Test #4:
score: -100
Time Limit Exceeded
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...