QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#399230 | #5445. Vulpecula | qwqUwU_ | WA | 21ms | 9512kb | C++17 | 3.1kb | 2024-04-26 07:51:55 | 2024-04-26 07:51:55 |
Judging History
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;
mt19937 gen(time(0));
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 ll read(){
ll x=0,f=1,c=getchar();
while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
const int mod=998244353;
inline int fp(int x,ll p=mod-2,int m=mod,int res=1){
for(;p;p>>=1){if(p&1)res=1ll*res*x%m;x=1ll*x*x%m;}
return res;
}
inline void plust(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
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],a[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(a[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--)a[i].insert(read(),0);
a[i].reverse();
t[i]=a[i];
}
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: 8188kb
input:
2 1 2 2 3 2 1 1
output:
4 2
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 8924kb
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: 8952kb
input:
2 1 0 0
output:
0 0
result:
ok 2 lines
Test #4:
score: -100
Wrong Answer
time: 21ms
memory: 9512kb
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'