QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#385716#5111. Take On MemeSolitaryDreamWA 1ms4628kbC++173.4kb2024-04-11 00:32:342024-04-11 00:32:34

Judging History

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

  • [2024-04-11 00:32:34]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4628kb
  • [2024-04-11 00:32:34]
  • 提交

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'