QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#155326 | #5445. Vulpecula | 275307894a | WA | 27ms | 129416kb | C++14 | 3.0kb | 2023-09-01 15:53:16 | 2023-09-01 15:53:17 |
Judging History
answer
#include<bits/stdc++.h>
#define Me(x,y) memset(x,y,sizeof x)
#define Mc(x,y) memcpy(x,y,sizeof x)
#define PB push_back
using ll=long long;using ull=unsigned long long;
const int N=5e4+5,M=N*4+5,mod=1e9+7;
using namespace std;
int n,m,k,x,y,z;
vector<int> S[N];
struct IO{
static const int S=1<<21;
char buf[S],*p1,*p2;int st[105],Top;
~IO(){clear();}
inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}
template<typename T>inline IO&operator >> (T&x){
x=0;bool f=0;char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
f?x=-x:0;return *this;
}
inline IO&operator << (const char c){pc(c);return *this;}
template<typename T>inline IO&operator << (T x){
if(x<0) pc('-'),x=-x;
do{st[++st[0]]=x%10,x/=10;}while(x);
while(st[0]) pc('0'+st[st[0]--]);return *this;
}
}fin,fout;
struct BB{
ull f[70];int d[70];BB(){Me(f,0);Me(d,0);}
void Ins(ull x,int y){for(int i=0;i<64;i++) if(x>>i&1){if(f[i]) y<d[i]&&(swap(y,d[i]),swap(x,f[i]),0),x^=f[i];else {f[i]=x;d[i]=y;return;}}}
ull GA(int D){
ull Ans=0;for(int i=63;~i;i--){
if(__builtin_popcountll(Ans&f[i])&1||!f[i]||d[i]>D) Ans|=1llu<<i;
} return Ans;
}
void add(){for(int i=63;~i;i--) if(f[i]) d[i]++;}
}f[N],Cl,Ans,g1[N],g2[N];
ull Hp[70];
BB Mg(BB A,BB B){for(int i=63;~i;i--) if(A.f[i]) B.Ins(A.f[i],A.d[i]);return B;}
void Ins(ull x){for(int i=63;~i;i--) if(x>>i&1) {if(Hp[i]) x^=Hp[i];else{Hp[i]=x;return;}}}
void dfs1(int x,int La){
g1[x]=f[x];for(int i:S[x]) if(i^La){
dfs1(i,x);BB p=g1[i];p.add();
g1[x]=Mg(g1[x],p);
}
}
void dfs2(int x,int La){
BB p;p=g2[x];p.add();for(int i:S[x]) if(i^La) g2[i]=p;
BB Ts=f[x];Ts.add();for(int i:S[x]) if(i^La) g2[i]=Mg(g2[i],Ts),p=g1[i],p.add(),p.add(),Ts=Mg(Ts,p);
Ts=Cl;reverse(S[x].begin(),S[x].end());for(int i:S[x]) if(i^La) g2[i]=Mg(g2[i],Ts),p=g1[i],p.add(),p.add(),Ts=Mg(Ts,p);
for(int i:S[x]) if(i^La) dfs2(i,x);
}
int B[70],Bh;
int main(){
int i,j,h,type;scanf("%d",&n);for(i=2;i<=n;i++) scanf("%d",&x),S[x].PB(i),S[i].PB(x);
for(i=1;i<=n;i++){
fin>>x;Me(Hp,0);ull y;while(x--) fin>>y,Ins(y);
for(j=63;~j;j--) if(Hp[j])for(h=63;h>j;h--) if(Hp[h]>>j&1) Hp[h]^=Hp[j];
for(j=0;j<64;j++) {
if(!Hp[j]){
f[i].f[j]|=1ull<<j;
for(h=63;h>j;h--) if(Hp[h]>>j&1) f[i].f[j]|=1ull<<h;
}
}
}
dfs1(1,0);dfs2(1,0);
g1[1]=Mg(g1[1],g2[1]);
for(i=1;i<=n;i++){
ull ToT=0;g1[i]=Mg(g1[i],g2[i]);Bh=0;
for(j=0;j<64;j++) if(g1[i].f[j]) B[++Bh]=g1[i].d[j];
B[++Bh]=n;sort(B+1,B+Bh+1);Bh=unique(B+1,B+Bh+1)-B-1;
for(j=1;j<Bh;j++) ToT+=g1[i].GA(B[j])*(ull)(B[j+1]-B[j]);
printf("%llu\n",ToT);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 128104kb
input:
2 1 2 2 3 2 1 1
output:
4 2
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 7ms
memory: 128104kb
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: 8ms
memory: 129416kb
input:
2 1 0 0
output:
0 0
result:
ok 2 lines
Test #4:
score: -100
Wrong Answer
time: 27ms
memory: 129124kb
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'