QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#217756 | #5111. Take On Meme | ucup-team1004# | WA | 0ms | 4196kb | C++14 | 1.6kb | 2023-10-17 11:54:16 | 2023-10-17 11:54:16 |
Judging History
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'