QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #402556 | #5445. Vulpecula | cqbzly | WA | 18ms | 8484kb | C++14 | 3.0kb | 2024-04-30 22:01:40 | 2024-04-30 22:01:40 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ull unsigned long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=50005;
int n,fa[N];
vector<int>G[N];
struct node{
ull x;
int d;
};
struct node0{
ull g[64];
node f[64];
void ins(ull x){
for(int i=63;i>=0;i--){
if(x>>i&1){
if(!g[i]){
g[i]=x;
return;
}
x^=g[i];
}
}
}
void ins0(node t){
for(int i=0;i<=63;i++){
if(t.x>>i&1){
if(!f[i].x){
f[i]=t;
return;
}
if(f[i].d>t.d)swap(f[i],t);
t.x^=f[i].x;
}
}
}
void build(){
for(int i=63;i>=0;i--){
for(int j=i-1;j>=0;j--){
if(g[i]>>j&1){
g[i]^=g[j];
}
}
}
for(int i=0;i<=63;i++){
if(!g[i]){
f[i].x|=1ull<<i;
for(int j=i+1;j<=63;j++){
if(g[j]>>i&1){
f[i].x|=1ull<<j;
}
}
}
}
}
ull ask(int d){
ull x=0;
for(int i=63;i>=0;i--){
if(f[i].x&&d>=f[i].d){
if(__builtin_parityll(x&f[i].x)){
x|=1ull<<i;
}
}else x|=1ull<<i;
}
return x;
}
}a[N];
void dfs(int u){
for(auto v:G[u]){
dfs(v);
for(int i=63;i>=0;i--){
if(a[v].f[i].x)a[u].ins0({a[v].f[i].x,a[v].f[i].d+1});
}
}
}
vector<int>vec;
ull res[N];
void dfs0(int u){
vec.clear(),vec.pb(n);
for(int i=0;i<=63;i++){
if(a[u].f[i].x){
vec.pb(a[u].f[i].d);
}
}
sort(vec.begin(),vec.end());
for(int i=0;i<vec.size()-1;i++){
if(vec[i]==vec[i+1])continue;
res[u]+=a[u].ask(vec[i])*(vec[i+1]-vec[i]);
}
for(auto v:G[u]){
for(int i=0;i<=63;i++){
if(a[u].f[i].x)a[v].ins0({a[u].f[i].x,a[u].f[i].d+1});
}
dfs0(v);
}
}
int main(){
//freopen("data.in","r",stdin);
// freopen("own.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=2;i<=n;i++){
cin>>fa[i],G[fa[i]].pb(i);
}
for(int i=1;i<=n;i++){
int K;cin>>K;
for(int j=1;j<=K;j++){
ull x;cin>>x;
a[i].ins(x);
}
a[i].build();
}
dfs(1);
dfs0(1);
// for(int i=0;i<=63;i++){
// if(a[2].f[i].x){
// cout<<"find:"<<i<<" "<<a[2].f[i].x<<" "<<a[2].f[i].d<<"\n";
// }
// }
// cout<<a[1].ask(0);
for(int i=1;i<=n;i++){
cout<<res[i]<<"\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 6016kb
input:
2 1 2 2 3 2 1 1
output:
4 2
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 4808kb
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: 4776kb
input:
2 1 0 0
output:
0 0
result:
ok 2 lines
Test #4:
score: -100
Wrong Answer
time: 18ms
memory: 8484kb
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:
18434153946472599290 17931933346714042066 17916198204903720384 17916198204176061150 17931933346710961779 18445169471807930489 17931926407666058065 18445169471807930349 17931933346714042064 17916198204176061020 18445169471807930489 18446738828973977866 17916198204176061018 17931926407666058065 184467...
result:
wrong answer 1st lines differ - expected: '18434153946472599289', found: '18434153946472599290'