Parabola Independence

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4const int inf = 1e9;
    5const long long INF = 1e17; //❄️
    6void solve() {
    7    int n; cin >> n;
    8    vector<ll> a(n), b(n), c(n);
    9    for (int i = 0; i < n; i++) {
    10        cin >> a[i] >> b[i] >> c[i];
    11    }
    12    vector<vector<int>> adj(n);
    13    vector<int> indegree(n);
    14    auto change = [&] (ll ai, ll bi, ll ci, ll aj, ll bj, ll cj, int &d) {
    15        ll a = ai - aj, b = bi - bj, c = ci - cj;
    16        if (a == 0) {
    17            if (b != 0) return false;
    18            d = (c < 0 ? -1 : 1);
    19            return true;
    20        }
    21        ll dis = b * b - 4LL * a * c;
    22        if (dis >= 0) return false;
    23        d = (a < 0 ? -1 : 1);
    24        return true;
    25    };
    26    for (int i = 0; i < n; i++) {
    27        for (int j = i + 1; j < n; j++) {
    28           int d = 0;
    29           if (!change(a[i], b[i], c[i], a[j], b[j], c[j], d)) continue;
    30           if (d == -1) {
    31                adj[i].push_back(j);
    32                indegree[j]++;
    33           } else {
    34                adj[j].push_back(i);
    35                indegree[i]++;
    36           }
    37        }
    38    }
    39    queue<int> q;
    40    for (int i = 0; i < n; i++) {
    41        if (indegree[i] == 0) q.push(i);
    42    }
    43    vector<int> topo;
    44    while (!q.empty()) {
    45        int u = q.front(); q.pop();
    46        topo.push_back(u);
    47        for (int v : adj[u]) {
    48            if (--indegree[v] == 0) q.push(v);
    49        }
    50    }
    51    vector<int> dp1(n, 1), dp2(n, 1);
    52    for (int u : topo) {
    53        for (int v : adj[u]) {
    54           dp2[v] = max(dp2[v], dp2[u] + 1); 
    55        }
    56    }
    57    for (int i = topo.size() - 1; i >= 0; i--) {
    58        int u = topo[i];
    59        for (int v : adj[u]) {
    60            dp1[u] = max(dp1[u], dp1[v] + 1);
    61        }
    62    }
    63    for (int i = 0; i < n; i++) {
    64        cout << dp1[i] + dp2[i] - 1 << " \n"[i == n - 1];
    65    }
    66}
    67int main() {
    68    ios::sync_with_stdio(0); cin.tie(0); 
    69    int t; cin >> t;
    70    while (t--) {
    71        solve();
    72    }
    73    return 0;
    74}