QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#217756#5111. Take On Memeucup-team1004#WA 0ms4196kbC++141.6kb2023-10-17 11:54:162023-10-17 11:54:16

Judging History

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

  • [2023-10-17 11:54:16]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4196kb
  • [2023-10-17 11:54:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
using vec=complex<ll>;
ll dot(const vec &a,const vec &b){
	return real(conj(a)*b);
}
const int N=1e4+10;
int n;
vector<int>to[N];
vec cur,a[N];
bool cmp(vec a,vec b){
	return dot(a,cur)<dot(b,cur);
}
pair<vec,vec> dfs(int u){
	if(to[u].empty())return {a[u],a[u]};
	vector<vec>p;
	vec sl,sr;
	for(int v:to[u]){
		vec l,r;
		tie(l,r)=dfs(v);
		p.push_back(l+r);
		sl+=l,sr+=r;
	}
	vec l=p.back()-sr,r=p.back()-sl;
	for(vec x:p)l=min(l,x-sr,cmp),r=min(r,x-sl,cmp);
	return {l,r};
}
ll ans;
pair<vec,vec> solve(vec cur){
	::cur=cur;
	auto res=dfs(1);
	ans=max({ans,norm(res.first),norm(res.second)});
	return res;
}
void find(vec l,vec r){
	vec p=(r-l)*vec(0,1),mid=solve(p).second;
	if(dot(p,mid)>max(dot(p,l),dot(p,r))){
		find(l,mid),find(mid,r);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1,k,x,y;i<=n;i++){
		scanf("%d",&k);
		if(!k){
			scanf("%d%d",&x,&y);
			a[i]=vec(x,y);
		}else{
			for(;k--;){
				scanf("%d",&x);
				to[i].push_back(x);
			}
		}
	}
	vec l,r;
	tie(l,r)=solve(vec(0,1));
	find(l,r);
	cout<<ans<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3836kb

input:

5
4 2 3 4 5
0 2 -2
0 1 3
0 4 -6
0 -18 5

output:

725

result:

ok single line: '725'

Test #2:

score: 0
Accepted
time: 0ms
memory: 4196kb

input:

5
2 2 3
2 4 5
0 1 5
0 -4 -6
0 -1 7

output:

340

result:

ok single line: '340'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3920kb

input:

18
3 4 3 2
2 5 6
3 7 9 8
3 10 11 12
0 4 -1
0 18 49
0 -2 10
2 13 14
0 -5 6
0 5 8
4 15 16 17 18
0 17 3
0 3 -9
0 -7 -1
0 14 -33
0 -23 11
0 11 14
0 2 19

output:

8125

result:

wrong answer 1st lines differ - expected: '26269', found: '8125'