QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#155345 | #5445. Vulpecula | qzez | TL | 2800ms | 57644kb | C++14 | 2.4kb | 2023-09-01 16:01:17 | 2023-09-01 16:01:17 |
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,Bas[v]=bas[v];
}
ob.push_back(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: 3ms
memory: 55032kb
input:
2 1 2 2 3 2 1 1
output:
4 2
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 14ms
memory: 55212kb
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: 55040kb
input:
2 1 0 0
output:
0 0
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 35ms
memory: 55108kb
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:
ok 500 lines
Test #5:
score: 0
Accepted
time: 1328ms
memory: 57564kb
input:
49999 1 1 3 1 1 5 2 4 1 8 7 6 3 13 4 12 12 1 19 8 2 16 23 6 21 3 11 1 21 7 14 6 3 28 31 24 6 22 27 11 17 25 41 5 17 13 1 48 17 14 31 18 43 30 53 27 7 39 4 2 11 55 48 17 32 15 24 44 53 63 70 31 21 17 74 37 34 48 15 33 14 53 8 9 72 10 65 77 69 36 32 61 51 63 77 25 71 47 59 94 39 41 77 24 5 33 43 18 72...
output:
18446744063446965319 18316893942693974299 18446744073709548919 18355577725686532847 18446744073709551614 18446744073709551615 18446744073709551614 18446744073709551615 18446736549671322125 12348860911474380074 18446744072601433415 18446744073709551615 17335313836902106838 18446744073709551576 184467...
result:
ok 49999 lines
Test #6:
score: 0
Accepted
time: 1362ms
memory: 57240kb
input:
50000 1 1 1 2 2 2 3 4 4 5 5 5 6 6 8 8 8 8 8 8 9 9 10 10 11 11 12 12 13 13 13 14 14 14 15 15 15 16 18 18 19 19 20 20 20 20 21 23 24 24 24 24 26 26 27 27 28 29 29 29 30 30 30 31 31 32 32 32 32 33 33 33 34 34 35 35 36 36 36 36 37 38 38 38 38 39 39 39 40 41 42 43 44 44 45 45 45 46 46 47 47 47 47 47 48 4...
output:
17388026687988753207 18446123107769912009 18433598785516292263 18446483694069646475 18446744073700722557 18446743950305151556 18446123107769912008 18446170606667738311 18446744071353497819 18446744065870877991 18446744073709531050 18446744073709231216 18446546425974411728 18446744073709533965 184467...
result:
ok 50000 lines
Test #7:
score: 0
Accepted
time: 1670ms
memory: 57340kb
input:
50000 1 1 3 4 5 6 5 7 3 10 6 12 12 12 5 8 17 4 19 20 17 22 22 22 25 25 27 27 28 22 31 31 31 34 34 35 37 38 38 40 41 42 43 42 44 46 40 42 47 50 50 40 53 41 42 56 57 58 59 59 61 62 59 64 65 65 59 61 69 62 71 72 73 72 72 74 58 62 79 80 79 82 74 84 84 84 46 72 89 90 90 34 93 94 94 96 94 95 95 100 101 10...
output:
68374895075 72669862370 64079927780 59784960485 55489993190 59784959085 64079926378 51195028691 68374893673 68374895075 72669862370 64079926376 68374893671 68374893671 68374893671 59784960485 46900064818 51195032113 64079927780 68374895075 72669862370 42605100943 46900068238 46900068216 46900068238 ...
result:
ok 50000 lines
Test #8:
score: 0
Accepted
time: 1185ms
memory: 56188kb
input:
25000 1 2 3 4 3 3 1 7 4 5 8 8 6 5 6 12 10 5 13 16 1 11 9 22 2 26 7 15 10 9 18 11 14 27 35 30 6 38 20 37 14 28 9 12 29 19 16 17 17 25 51 52 23 24 45 56 17 33 31 32 13 62 21 33 18 5 67 20 41 58 61 34 31 19 25 28 75 76 24 23 27 36 19 6 85 15 14 50 49 54 29 81 23 79 32 82 97 53 40 42 66 46 30 78 40 43 8...
output:
18446744070444123456 18446744051208917090 18446744073687263354 18446744073709551561 18446742841285205723 18446175471565024345 18446744041357423475 18371821048696416150 18446743733103011459 18446744058754418143 18446744073615083416 18438543872624704476 18428215314831608530 18146245131772760630 184467...
result:
ok 25000 lines
Test #9:
score: 0
Accepted
time: 98ms
memory: 57644kb
input:
50000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 50000 lines
Test #10:
score: 0
Accepted
time: 244ms
memory: 57488kb
input:
50000 1 2 2 4 5 6 7 8 8 10 10 11 9 14 15 15 16 18 19 13 20 22 22 21 25 26 27 28 28 4 31 32 32 34 35 36 37 38 39 40 37 42 43 44 45 45 40 48 49 50 49 52 52 41 55 55 57 56 38 60 61 62 63 64 63 50 48 68 69 69 62 72 73 72 75 68 77 56 19 44 81 82 83 82 83 61 87 87 89 90 89 92 18 94 95 96 94 98 99 96 95 10...
output:
18446744073709551601 18446744073709551602 18446744073709551603 18446744073709551603 18446744073709551604 18446744073709551605 18446744073709551606 18446744073709551607 18446744073709551608 18446744073709551608 18446744073709551609 18446744073709551607 18446744073709551610 18446744073709551609 184467...
result:
ok 50000 lines
Test #11:
score: 0
Accepted
time: 2800ms
memory: 57292kb
input:
50000 1 1 3 4 5 2 7 8 6 9 11 12 10 14 13 15 16 17 18 19 21 20 22 24 23 25 27 26 28 30 31 32 33 34 29 35 37 36 38 40 41 39 42 44 43 45 46 48 47 50 49 52 53 51 55 56 54 57 58 59 60 62 61 64 65 66 67 68 69 70 63 71 72 74 73 76 75 78 77 79 80 81 82 83 84 85 86 87 88 89 90 92 91 93 94 96 97 98 95 99 101 ...
output:
18367844186012628696 18367842430297867877 18367845941602017631 18367847696870482250 18367849452065176591 18367851207243104606 18367840674674503782 18367838919205517572 18367837164020295681 18367852674316374835 18367835408823989376 18367833653098428815 18367831897383952668 18367854141296903375 183678...
result:
ok 50000 lines
Test #12:
score: 0
Accepted
time: 1519ms
memory: 57236kb
input:
50000 1 2 1 4 5 6 7 8 9 10 3 12 13 14 15 16 17 18 19 20 21 11 23 24 22 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 25 51 52 53 54 55 56 57 58 59 60 61 62 63 64 50 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...
output:
11830693669206161426 15555323927066560228 835488532647364820 7363753604854029059 2894535118950984022 16874499773021899126 12292344295621663824 2102496437386641629 10354835809796005713 162709530062143497 8417327324005152592 4562471278575433430 8264626372817797937 11957077303114769622 1557751198611634...
result:
ok 50000 lines
Test #13:
score: 0
Accepted
time: 2026ms
memory: 57288kb
input:
50000 1 2 1 3 5 6 4 8 9 7 11 10 13 14 12 15 16 18 17 20 21 19 22 23 24 26 27 25 28 30 29 31 32 33 35 36 34 38 37 40 39 41 43 42 45 46 47 48 49 50 51 52 44 53 55 56 57 58 59 54 61 62 63 60 65 66 67 64 68 70 71 72 73 69 74 75 76 78 77 80 81 82 83 84 79 86 85 87 89 88 90 91 93 94 92 95 96 98 99 100 101...
output:
16810415591965710206 5275813827366931639 12187956060199693517 9898273769935206067 653336450317114274 7565460974601185858 14477586125848329007 2986131906626164386 14520727293949990938 7608579144925250248 2942966458731584974 9855075192825865421 696430430531850340 12231025207124581077 53188757511752785...
result:
ok 50000 lines
Test #14:
score: -100
Time Limit Exceeded
input:
31313 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...