QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#189253 | #5111. Take On Meme | bulijiojiodibuliduo# | WA | 1ms | 4184kb | C++17 | 4.0kb | 2023-09-27 05:19:44 | 2023-09-27 05:19:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
//typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
typedef long long db;
const db EPS = 0;
inline int sign(db a) { return a < -EPS ? -1 : a > EPS; }
inline int cmp(db a, db b){ return sign(a-b); }
struct P {
db x, y;
P() {}
P(db _x, db _y) : x(_x), y(_y) {}
P operator+(P p) { return {x + p.x, y + p.y}; }
P operator-(P p) { return {x - p.x, y - p.y}; }
P operator*(db d) { return {x * d, y * d}; }
P operator/(db d) { return {x / d, y / d}; }
bool operator<(P p) const {
int c = cmp(x, p.x);
if (c) return c == -1;
return cmp(y, p.y) == -1;
}
bool operator==(P o) const{
return cmp(x,o.x) == 0 && cmp(y,o.y) == 0;
}
db dot(P p) { return x * p.x + y * p.y; }
db det(P p) { return x * p.y - y * p.x; }
db abs2() { return x * x + y * y; }
P rot90() { return P(-y,x);}
int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
};
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))
vector<P> convexHull(vector<P> ps) {
int n = ps.size(); if(n <= 1) return ps;
sort(ps.begin(), ps.end());
vector<P> qs(n * 2); int k = 0;
for (int i = 0; i < n; qs[k++] = ps[i++])
while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
qs.resize(k - 1);
return qs;
}
vector<P> merge(vector<P> a,vector<P> b) {
rotate(a.begin(),min_element(a.begin(), a.end()),a.end());
rotate(b.begin(),min_element(b.begin(), b.end()),b.end());
vector<P> c;
int p1=0,p2=0;
while (p1<SZ(a)||p2<SZ(b)) {
c.pb(a[p1%SZ(a)]+b[p2%SZ(b)]);
if (p1<SZ(a)&&p2<SZ(b)&&(a[(p1+1)%SZ(a)]-a[p1]).det(b[(p2+1)%SZ(b)]-b[p2])==0) {
p1++;
p2++;
} else if (p2==SZ(b)||(p1<SZ(b)&&(a[(p1+1)%SZ(a)]-a[p1]).det(b[(p2+1)%SZ(b)]-b[p2]))>0) {
p1++;
} else {
p2++;
}
}
/*
puts("merge");
for (auto p:a) printf("(%lld,%lld) ",p.x,p.y); puts("");
for (auto p:b) printf("(%lld,%lld) ",p.x,p.y); puts("");
for (auto p:c) printf("(%lld,%lld) ",p.x,p.y); puts("");*/
return c;
}
const int N=10100;
vector<P> ch[N];
VI son[N];
int n;
vector<P> neg(vector<P> ps) {
for (auto &p:ps) p=p*(-1);
reverse(all(ps));
return ps;
}
void gao(int u) {
if (son[u].empty()) {
return;
}
for (auto v:son[u]) gao(v);
function<pair<vector<P>,vector<P>>(int,int)> solve=[&](int l,int r) {
if (l==r) {
int v=son[u][l];
auto p1=ch[v],p2=neg(ch[v]);
return mp(p1,p2);
} else {
int md=(l+r)>>1;
auto [p1,p2]=solve(l,md);
auto [q1,q2]=solve(md+1,r);
auto r2=merge(p2,q2);
auto r11=merge(p1,q2);
auto r12=merge(p2,q1);
r11.insert(r11.end(),all(r12));
auto r1=convexHull(r11);
/*
printf("Solve %d %d\n",l,r);
for (auto p:r1) printf("(%lld,%lld) ",p.x,p.y); puts("");
for (auto p:r2) printf("(%lld,%lld) ",p.x,p.y); puts("");*/
return mp(r1,r2);
}
};
auto [r1,r2]=solve(0,SZ(son[u])-1);
ch[u]=r1;
}
int main() {
scanf("%d",&n);
rep(i,1,n+1) {
int k;
scanf("%d",&k);
if (k>0) {
rep(j,0,k) {
int x;
scanf("%d",&x);
son[i].pb(x);
}
} else {
int x,y;
scanf("%d%d",&x,&y);
ch[i].pb(P(x,y));
}
}
gao(1);
db ans=0;
for (auto [x,y]:ch[1]) ans=max(ans,x*x+y*y);
printf("%lld\n",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4184kb
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: 4128kb
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: 4128kb
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:
21541
result:
wrong answer 1st lines differ - expected: '26269', found: '21541'