QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#155345#5445. VulpeculaqzezTL 2800ms57644kbC++142.4kb2023-09-01 16:01:172023-09-01 16:01:17

Judging History

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

  • [2023-09-01 16:01:17]
  • 评测
  • 测评结果:TL
  • 用时:2800ms
  • 内存:57644kb
  • [2023-09-01 16:01:17]
  • 提交

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...

output:


result: