QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#399234#5445. VulpeculaqwqUwU_WA 24ms6972kbC++172.8kb2024-04-26 08:02:142024-04-26 08:02:15

Judging History

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

  • [2024-04-26 08:02:15]
  • 评测
  • 测评结果:WA
  • 用时:24ms
  • 内存:6972kb
  • [2024-04-26 08:02:14]
  • 提交

answer

// clang-format off
#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define bit(s,x) (((s)>>(x))&1)
#define pnp(s) __builtin_popcountll(s)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll; 
typedef unsigned long long ull; 
typedef pair<int,int> pii; typedef pair<ll,int> pli; typedef pair<ll,ll> pll; typedef pair<int,ll> pil;
inline ull read(){
	ull x=0,c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}
const int N=5e4+3;
const int M=64;
// clang-format on
int n;
vector<int>G[N];
ull ans=0;
struct basis{
	ull a[M];
	int ord[M];
	inline void insert(ull x,int od){
		if(!x)return;
		per(i,M-1,0)if(bit(x,i)){
			if(!a[i]){a[i]=x,ord[i]=od;return ;}
			if(ord[i]>od)swap(od,ord[i]),swap(x,a[i]);
			x^=a[i];
		}
	}
	inline void insert2(ull x,int od){
		if(!x)return;
		rep(i,0,M-1)if(bit(x,i)){
			if(!a[i]){a[i]=x,ord[i]=od;return ;}
			if(ord[i]>od)swap(od,ord[i]),swap(x,a[i]);
			x^=a[i];
		}
	}
	inline void reverse(){
		per(i,M-1,0)per(j,i-1,0)if(bit(a[i],j))a[i]^=a[j];
		static ull b[M];
		per(i,M-1,0)if(!a[i]){
			b[i]=1llu<<i;
			per(j,M-1,i+1)if(bit(a[j],i))b[i] |= 1llu<<j;
		}
		rep(i,0,M-1)a[i]=b[i];
		memset(b,0,sizeof b);
		memset(ord,0,sizeof ord);
	}
	inline void query(){// in reverse
		static int id[M];rep(i,0,M-1)id[i]=i;
		sort(id,id+M,[&](int i,int j){return ord[i]<ord[j];});
		static bool inq[M];memset(inq,0,sizeof inq);
		rep(i,0,M-1){
			inq[id[i]]=1; ull x=(M==64?(~0):(1llu<<M)-1);
			per(j,M-1,0)if(inq[j]) x^=(pnp(a[j]&x)&1ll)<<j;
			ans += ((i==M-1?n:ord[id[i+1]])-ord[id[i]])*x;
		}
	}
	inline void merge(const basis &A,int d=1){
		rep(i,0,M-1)insert2(A.a[i],A.ord[i]+d);
	}
	inline void clear(){
		memset(a,0,sizeof a);
		memset(ord,0,sizeof ord);
	}
}t[N],out,suf[N];
int fa[N];
ull res[N];
inline void dfs(int u){
	ans=0;
	basis bs=t[u];bs.merge(out);bs.query();
	res[u]=ans;
	if(G[u].empty())return ;
	basis old=out;
	rep(i,0,M-1)if(out.a[i])++out.ord[i];
	out.merge(t[u],0);
	per(i,(int)G[u].size()-2,0){
		suf[G[u][i]]=suf[G[u][i+1]];
		suf[G[u][i]].merge(t[G[u][i+1]],0);
	}
	basis pre;pre.clear();
	rep(i,0,G[u].size()-1){
		basis tmp=out;
		out.merge(pre);
		out.merge(suf[G[u][i]]);
		dfs(G[u][i]);
		out=tmp;
		pre.merge(t[G[u][i]],0);
	}
	out=old;
}
int main() {
    //freopen("data.in", "r", stdin);
    // freopen(".in","r",stdin);
    // freopen("myans.out","w",stdout);
	n=read();rep(i,2,n)G[fa[i]=read()].pb(i);
	rep(i,1,n){
		int m=read();
		while(m--)t[i].insert(read(),0);
		t[i].reverse();
	}
	per(i,n,2)t[fa[i]].merge(t[i]);
	dfs(1);
	rep(i,1,n)printf("%llu\n",res[i]);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 6416kb

input:

2
1
2 2 3
2 1 1

output:

4
2

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 4972kb

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: 1ms
memory: 6972kb

input:

2
1
0
0

output:

0
0

result:

ok 2 lines

Test #4:

score: -100
Wrong Answer
time: 24ms
memory: 5992kb

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'