QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#189253#5111. Take On Memebulijiojiodibuliduo#WA 1ms4184kbC++174.0kb2023-09-27 05:19:442023-09-27 05:19:46

Judging History

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

  • [2023-09-27 05:19:46]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4184kb
  • [2023-09-27 05:19:44]
  • 提交

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'