QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#155298#5445. VulpeculaqzezTL 36ms55112kbC++142.4kb2023-09-01 15:28:052023-09-01 15:28:06

Judging History

你现在查看的是测评时间为 2023-09-01 15:28:06 的历史记录

  • [2023-09-01 15:34:37]
  • 管理员手动重测该提交记录
  • 测评结果:TL
  • 用时:2615ms
  • 内存:57328kb
  • [2023-09-01 15:28:06]
  • 评测
  • 测评结果:0
  • 用时:36ms
  • 内存:55112kb
  • [2023-09-01 15:28:05]
  • 提交

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)