QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#361637 | #5111. Take On Meme | JerryTcl | WA | 0ms | 3844kb | C++20 | 2.5kb | 2024-03-23 12:19:34 | 2024-03-23 12:19:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
template<typename T1, typename T2> struct Pair {
T1 x; T2 y; Pair(T1 X = T1(), T2 Y = T2()) : x(X), y(Y) {}
Pair operator + (const Pair o) const { return Pair(x + o.x, y + o.y); }
template<typename U> Pair operator * (const U o) const { return Pair(x * o, y * o); }
template<typename U> friend Pair operator * (const U p, const Pair q) { return q * p; }
Pair operator - () const { return (*this) * -1; }
Pair operator - (const Pair o) const { return (*this) + (-o); }
void operator += (const Pair o) { (*this) = (*this) + o; }
void operator -= (const Pair o) { (*this) = (*this) - o; }
int operator < (const Pair o) const { return x == o.x ? y < o.y : x < o.x; }
friend istream &operator >> (istream &is, Pair &o) { return is >> o.x >> o.y; }
friend ostream &operator << (ostream &os, const Pair o) { return os << "(" << o.x << ", " << o.y << ")"; }
};
typedef Pair<int, int> Pnt, Vec; typedef const Pnt cPnt, cVec;
inline Vec Rot90(cVec p) { return Pnt(p.y, -p.x); }
inline int64 Dot(cVec a, cVec b) { return 1ll * a.x * b.x + 1ll * a.y * b.y; }
inline int64 Cro(cVec a, cVec b) { return 1ll * a.x * b.x + 1ll * a.y * b.y; }
inline int64 Len2(cVec a) { return Dot(a, a); }
inline int64 Lft(cPnt p, cPnt a, cPnt b) { return Cro(p - a, b - a) < 0; }
template<typename Fp> void Work(cPnt A, cPnt B, const Fp f) {
cPnt C = f(Rot90(B - A)); if(Lft(C, A, B)) Work(A, C, f), Work(C, B, f); }
int main() {
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n; vector<Vec> val(n);
vector<vector<int>> son(n); int64 ans = 0;
vector<Pair<int64, Vec>> fmin(n), fmax(n);
for(int i = 0, s; i < n; ++i) {
cin >> s; if(!s) { cin >> val[i]; continue; }
son[i].resize(s); for(int &v : son[i]) cin >> v, --v;
}
const auto solve = [&](cVec dir) {
const auto &dfs = [&](auto &&self, int x) -> void {
if(son[x].empty()) { fmin[x] = fmax[x] = {Dot(val[x], dir), val[x]}; return; }
Pair<int64, Vec> smn, smx, mn(LLONG_MAX), mx(LLONG_MIN);
for(int y : son[x]) self(self, y), smn += fmin[y], smx += fmax[y],
mn = min(mn, fmin[y] + fmax[y]), mx = max(mx, fmin[y] + fmax[y]);
fmin[x] = mn - smx, fmax[x] = mx - smn;
};
dfs(dfs, 0), ans = max(ans, Len2(fmax[0].y)); return fmax[0].y;
};
const Pnt L = solve(Vec(-1, 0)), R = solve(Vec(1, 0));
Work(L, R, solve), Work(R, L, solve), printf("%lld", ans);
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3788kb
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: 3792kb
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: 3844kb
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'