QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#361637#5111. Take On MemeJerryTclWA 0ms3844kbC++202.5kb2024-03-23 12:19:342024-03-23 12:19:39

Judging History

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

  • [2024-03-23 12:19:39]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3844kb
  • [2024-03-23 12:19:34]
  • 提交

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'