WF2022K.cc

#include <bits/stdc++.h>
using int64 = long long;
const int N = 10005;

struct Point {
  int x, y;
  Point(int x = 0, int y = 0) : x(x), y(y) {}
  bool operator<(const Point& rhs) {
    return x != rhs.x ? x < rhs.x : y < rhs.y;
  }
  Point operator+(const Point& rhs) {
    return Point(x + rhs.x, y + rhs.y);
  }
  Point operator-(const Point& rhs) {
    return Point(x - rhs.x, y - rhs.y);
  }
  int64 operator^(const Point& rhs) {
    return 1LL * x * rhs.y - 1LL * y * rhs.x;
  }
};
typedef std::vector<Point> Polygon;
Polygon operator+(Polygon a, Polygon b) {
  Polygon res;
  assert(std::min_element(a.begin(), a.end()) == a.begin());
  assert(std::min_element(b.begin(), b.end()) == b.begin());
  int n = a.size(), m = b.size();
  a.emplace_back(a[0]);
  a.emplace_back(a[1]);
  b.emplace_back(b[0]);
  b.emplace_back(b[1]);
  for (int i = 0, j = 0; i < n || j < m;) {
    res.push_back(a[i] + b[j]);
    int64 cross = (a[i + 1] - a[i]) ^ (b[j + 1] - b[j]);
    i += (i < n && cross >= 0);
    j += (j < m && cross <= 0);
  }
  return res;
}
Polygon operator-(Polygon& a) {
  Polygon res = a;
  for (auto& p : res) {
    p.x = -p.x;
    p.y = -p.y;
  }
  std::rotate(res.begin(), std::min_element(res.begin(), res.end()), res.end());
  return res;
}
inline int64 OnLeft(Point P, Point A, Point B) {
  return (B - A) ^ (P - A);
}
Polygon convex(std::vector<Point>& p) {
  std::sort(p.begin(), p.end());
  Polygon s;
  for (int i = 0; i < p.size(); ++i) {
    while (s.size() > 1 &&
           OnLeft(p[i], s[s.size() - 2], s[s.size() - 1]) <= 0) {
      s.pop_back();
    }
    s.emplace_back(p[i]);
  }
  int tmp = s.size();
  for (int i = (int)p.size() - 2; i >= 0; --i) {
    while (s.size() > tmp &&
           OnLeft(p[i], s[s.size() - 2], s[s.size() - 1]) <= 0) {
      s.pop_back();
    }
    s.emplace_back(p[i]);
  }
  if (p.size() > 1) {
    s.pop_back();
  }
  return s;
}
std::vector<std::vector<int>> e;
int X[N], Y[N];
Polygon dfs(int x) {
  if (e[x].empty()) {
    return Polygon(1, Point(X[x], Y[x]));
  }
  std::vector<Polygon> pre, cur;
  pre.push_back(Polygon(1, Point(0, 0)));
  for (auto& y : e[x]) {
    cur.push_back(dfs(y));
    pre.push_back(pre.back() + -cur.back());
  }
  Polygon suf = Polygon(1, Point(0, 0));
  std::vector<Point> points;
  for (int i = cur.size() - 1; i >= 0; --i) {
    for (auto p : pre[i] + cur[i] + suf) {
      points.emplace_back(p);
    }
    suf = -cur[i] + suf;
  }
  return convex(points);
}

void work() {
  int n;
  scanf("%d", &n);
  e.resize(n + 1);
  for (int i = 1; i <= n; ++i) {
    int k;
    scanf("%d", &k);
    if (k == 0) {
      scanf("%d%d", &X[i], &Y[i]);
    } else {
      e[i].resize(k);
      for (int j = 0; j < k; ++j) {
        scanf("%d", &e[i][j]);
      }
    }
  }
  int64 res = 0;
  for (auto& p : dfs(1)) {
    res = std::max(res, 1LL * p.x * p.x + 1LL * p.y * p.y);
  }
  printf("%lld\n", res);
}

int main() {
  int T = 1;
  // scanf("%d", &T);
  while (T--) {
    work();
  }
  return 0;
}