QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#385716 | #5111. Take On Meme | SolitaryDream | WA | 1ms | 4628kb | C++17 | 3.4kb | 2024-04-11 00:32:34 | 2024-04-11 00:32:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fs first
#define sd second
const int N=1e4+1e3+7;
struct P {
int x, y, id;
};
int operator *(const P &a,const P &b)
{
return a.x*b.y-a.y*b.x;
}
bool operator <(const P &a,const P &b)
{
int da=a.x>0||(a.x==0&&a.y>0),db=b.x>0||(b.x==0&&b.y>0);
if(da!=db)
return da>db;
return a*b>0;
}
using cv=pair<P, vector<P> >;
cv f[N];
P operator -(const P &a)
{
return {-a.x,-a.y};
}
P operator -(const P &a,const P &b)
{
return {a.x-b.x,a.y-b.y};
}
P operator +(const P &a,const P &b)
{
return {a.x+b.x,a.y+b.y};
}
// cv operator +(const cv &a,const cv &b)
// {
// }
int n;
vector<int> g[N];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
int k;
cin>>k;
if(k)
{
while(k--)
{
int a;
cin>>a;
g[i].push_back(a);
}
}
else
{
cin>>f[i].fs.x>>f[i].fs.y;
// f[i].sd.push_back({0,0,i});
}
}
for(int i=n;i>=1;i--)
{
if(!g[i].size())
continue;
vector<P> all;
cv tmp;
for(auto v:g[i])
{
tmp.fs=tmp.fs+f[v].fs;
for(auto p:f[v].sd)
tmp.sd.push_back(p);
}
for(auto v:g[i])
{
vector<P> tv;
P base=-(tmp.fs-f[v].fs);
for(auto p:tmp.sd)
if(p.id!=v)
{
tv.push_back(-p);
if(p.x>0||(p.x==0&&p.y>0))
base=base-p;
}
base=base+f[v].fs;
int m=tv.size();
for(auto q:f[v].sd)
tv.push_back(q);
sort(tv.begin(),tv.end());
// inplace_merge(tv.begin(),tv.begin()+m,tv.end());
all.push_back(base);
for(auto x:tv)
base=base+x,all.push_back(base);
}
sort(all.begin(),all.end(),[&](const P &a,const P &b){return a.x<b.x||(a.x==b.x&&a.y<b.y);});
// all.erase(unique(all.begin(),all.end(),[&](const P &a,const P &b){return a.x==b.x&&a.y==b.y;}),all.end());
vector<P> st;
for(auto p:all)
{
while(st.size()>1&&(p-st.end()[-2])*(st.back()-st.end()[-2])>=0)
st.pop_back();
st.push_back(p);
}
int k=st.size();
reverse(all.begin(),all.end());
for(auto p:all)
{
while(st.size()>k&&(p-st.end()[-2])*(st.back()-st.end()[-2])>=0)
st.pop_back();
st.push_back(p);
}
f[i].first=st[0];
if(st.size()>1)
{
for(int t=0;t<st.size();t++)
{
auto v=st[(t+1)%st.size()]-st[t];
// assert(v.x||v.y);
f[i].sd.push_back(v);
}
}
sort(f[i].sd.begin(),f[i].sd.end());
for(auto &p:f[i].sd)
p.id=i;
}
int ans=0;
P base=f[1].fs;
ans=max(ans,base.x*base.x+base.y*base.y);
for(auto x:f[1].sd)
{
base=base+x;
ans=max(ans,base.x*base.x+base.y*base.y);
}
cout<<ans<<"\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4424kb
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: 1ms
memory: 4628kb
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: 1ms
memory: 4380kb
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:
25857
result:
wrong answer 1st lines differ - expected: '26269', found: '25857'