QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#155298 | #5445. Vulpecula | qzez | TL | 36ms | 55112kb | C++14 | 2.4kb | 2023-09-01 15:28:05 | 2023-09-01 15:28:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
ostream& operator << (ostream &out,vector<auto>x){
out<<'[';
if(!x.empty())out<<x[0];
for(size_t i=1;i<x.size();i++)out<<','<<x[i];
return out<<']';
}
void Debug(char *a,auto x){
cerr<<a<<'='<<x<<endl;
}
void Debug(char *a,auto x,auto... y){
for(int t=0;*a!=','||t;cerr<<*a++)
t+=*a=='('||*a=='{',t-=*a==')'||*a=='}';
cerr<<'='<<x<<',',Debug(a+1,y...);
}
template<typename Tp>
auto ary(Tp *l,Tp *r){
return vector<Tp>{l,r};
}
#define debug(...) Debug((char*)#__VA_ARGS__,__VA_ARGS__)
using ll=long long;
using ull=unsigned long long;
const int N=5e4+10,M=64;
struct basis{
ull a[M];
basis(){
memset(a,0,sizeof a);
}
bool insert(ull x){
for(int i=M-1;~i;i--)
if(x>>i&1)
if(a[i])x^=a[i];
else return a[i]=x,1;
return 0;
}
void gauss(){
for(int i=0;i<M;i++)if(a[i])
for(int j=0;j<i;j++)if(a[j])
if(a[i]>>j&1)a[i]^=a[j];
}
ull calc(){
ull ans=0;
for(int i=M-1;~i;i--)ans=max(ans,ans^a[i]);
return ans;
}
bool operator != (const basis &x)const{
for(int i=0;i<M;i++)if(a[i]!=x.a[i])return 1;
return 0;
}
};
basis merge(basis x,basis y){
// debug("merge",x.calc(),y.calc());
basis las=x,ans;
for(int i=0;i<M;i++)if(y.a[i]){
ull t=0,p=y.a[i];
for(int j=i;~j;j--)if(p>>j&1)
if(las.a[j])p^=las.a[j],t^=x.a[j];
else{
las.a[j]=p,x.a[j]=t,t=0;break;
}
ans.insert(t);
}
// debug("merge",ans.calc());
return ans;
}
int n,cur[N];
basis bas[N],Bas[N];
vector<int>oa,ob,to[N];
ull ans[N];
void read(ull &x){
char c;
for(x=0;!isdigit(c=getchar()););
for(;x=(x<<3)+(x<<1)+(c^48),isdigit(c=getchar()););
}
int main(){
scanf("%d",&n);
for(int i=2,x;i<=n;i++){
scanf("%d",&x);
to[x].push_back(i),to[i].push_back(x);
}
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
for(ull y;x--;)read(y),bas[i].insert(y);
// debug(i,bas[i].calc());
oa.push_back(i);
}
for(int i=1;i<=n;i++){
// debug(i,oa);
ob.clear();
for(int u:oa)for(int v:to[u]){
if(cur[v]<i){
ans[v]+=bas[v].calc()*(i-cur[v]);
cur[v]=i,ob.push_back(v),Bas[v]=bas[v];
}
Bas[v]=merge(Bas[v],bas[u]);
}
oa.clear();
// debug(i,ob);
for(int u:ob){
Bas[u].gauss();
// debug(u,Bas[u].calc());
if(bas[u]!=Bas[u])bas[u]=Bas[u],oa.push_back(u);
}
}
for(int i=1;i<=n;i++)ans[i]+=bas[i].calc()*(n-cur[i]);
for(int i=1;i<=n;i++)printf("%llu\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 9ms
memory: 55040kb
input:
2 1 2 2 3 2 1 1
output:
4 2
result:
ok 2 number(s): "4 2"
Test #2:
score: 0
Accepted
time: 4ms
memory: 55084kb
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 number(s): "171 125 183 142 243"
Test #3:
score: 0
Accepted
time: 3ms
memory: 55112kb
input:
2 1 0 0
output:
0 0
result:
ok 2 number(s): "0 0"
Test #4:
score: -100
Wrong Answer
time: 36ms
memory: 54944kb
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:
18434153946472599289 17931933346714042066 17916198204903720383 17916198204176061148 17931933346710961779 18445169471807930489 17931926407666058065 18445169471807930348 17931933346714042064 17916198204176061019 18445169471807930488 18446738828973977865 17916198204176061018 17931926407666058064 184467...
result:
FAIL Expected int64, but "18434153946472599289" found (/var/uoj_data/5445/4.ans)