QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#155326#5445. Vulpecula275307894aWA 27ms129416kbC++143.0kb2023-09-01 15:53:162023-09-01 15:53:17

Judging History

你现在查看的是最新测评结果

  • [2023-09-01 15:53:17]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:129416kb
  • [2023-09-01 15:53:16]
  • 提交

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'