Opis glavnog rešenja

Neka je tabela \(\mathbf{T} = (t_{i,j})\) takva da je \(t_{i,j}\) godina kada je \(j\)-ti vladara \(i\)-te nacije počeo da vlada. Drugim rečima, \(j\)-ti vladar \(i\)-te nacije je vladao u intervalu \([t_{i,j}, t_{i,j+1})\). Bitke čuvamo u nizu uređenih četvorki \((n_1, v_1, n_2, v_2)_{1 \leq i \leq n}\), gde \((n_i, v_i)\) predstavlja \(v_i\)-tog vladara nacije \(n_i\).

Neka je \(y_i\) početna godina \(i\)-te nacije, tj. \(y_i\) godine nastaje nacija \(i\). Mogu postojati razne vrednosti za početnu godinu \(y_i\). Zbog toga nas neće zanimati konkretna vrednosti \(y_i\) već nam ona omogućava da definišemo razliku početnih godina dve nacije \(x_{i, j} = y_j - y_i\).

Posmatramo dalje bitku \((n_1, v_1, n_2, v_2)\). Kako se bitka odvijala između \(v_1\)-og vladara nacije \(n_1\) i \(v_2\)-og vladara nacije \(n_2\) postoji zajednički period, od bar jedne godine, u kome su oni vladali. To znači da postoji neprazan presek između sledeća dva intervala:

\[ [y_{n_1} + t_{n_1, v_1}, y_{n_1} + t_{n_1, v_1 + 1}) \\ [y_{n_2} + t_{n_2, v_2}, y_{n_2} + t_{n_2, v_2 + 1}) \]

Kako mogu postojati razne vrednosti \(y_{n_1}\) i \(y_{n_2}\) prethodna dva intervala zapisujemo preko razlike početnih godina \(x_{n_1, n_2} = y_{n_2} - y_{n_1}\) kao:

\[ [t_{n_1, v_1}, t_{n_1, v_1 + 1}) \\ [x_{n_1, n_2} + t_{n_2, v_2}, x_{n_1, n_2} + t_{n_2, v_2 + 1}) \]

Kako intervali moraju imati neprazan presek, validne vrednosti promenljive \(x_{n_1, n_2}\) su uzastopne i ograničene. To pokazuje sledeća slika:

Treba odrediti donju i gornju granicu za \(x_{n_1, n_2}\). Sa slike, možemo primetiti da se najmanja moguća vrednosti za \(x_{n_1, n_2}\) dobija kada se drugi interval nalazi najlevlje u odnosu na prvi, tj. važi \(t_{n_1, v_1} = x_{n_1, n_2} + t_{n_2, v_2 + 1} - 1\). Odatle imamo da je \(\min\{x_{n_1, n_2}\} = t_{n_1, v_1} - t_{n_2, v_2 + 1} + 1\). Sa druge strane, sa slike, možemo primetiti da se najveća moguća vrednost za \(x_{n_1, n_2}\) dobija kada se drugi interval nalazi najdesnije u odnosu na prvi, tj. važi \(t_{n_1, v_1 + 1} - 1 = x_{n_1, n_2} + t_{n_2, v_2}\). Odatle imamo da je \(\max\{x_{n_1, n_2}\} = t_{n_1, v_1 + 1} - t_{n_2, v_2} - 1\). Bitke su simetrične u odnosu na nacije, te važi da će minimalna vrednost za \(x_{n_1, n_2}\) biti \(\min\{x_{n_1, n_2}\}\), a minimalna vrednost za \(x_{n_2, n_1}\) je \(-\max\{x_{n_1, n_2}\}\). Iz ovih vrednosti možemo, takođe, pronaći odgovarajuće maksimalne vrednosti za \(x_{n_1, n_2}\) i \(x_{n_2, x_1}\).

Zbog dosadašnjeg razmatranja svaka bitka između nacija \(i\) i \(j\) uvodi novo ograničenje na \(x_{i,j}\) i \(x_{j,i}\), tj. imamo ograničenje da je \(x_{i,j} \geq a\). Kada objedinima sva ta ograničenja imamo da je \(x_{i,j} \geq \max \{ a_1, a_2, \ldots \}\). Zbog toga, za svake dve nacije \(i\) i \(j\), uvodimo novu promenljivu \(m_{i,j}\) koja predstavlja najmanju moguću vrednost promenljive \(x_{i,j}\). Kako je \(m_{i,j}\) najmanja moguća vrednost za \(x_{i,j}\), onda je \(- m_{j,i}\) najveća moguća vrednost za \(x_{i,j}\). Tada za svaki par nacija \(i\) i \(j\) ako važi \(- m_{j,i} < m_{i,j}\) znamo da je došlo do nekonzistentnosti. Drugi način podrazumeva da \(m_{i,i}\) može biti najviše nula, jer u suprotnom postoji više različitih početnih godina nacije \(i\), te znamo da je došlo do nekonzistentnosti.

Postoji tranzitivnosti između najmanjih mogućih vrednosti razlike početnih godine, i to \(m_{i,j}\) mora da bude bar \(m_{i,k} + m_{k,j}\). Zbog toga možemo iskoristiti Flojd-Varšalov algoritam za određivanje vrednosti \(m_{i,j}\).

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

struct Battle {
    int nation_1;
    int monarch_1;
    int nation_2;
    int monarch_2;
};

void add_constraint(vector<vector<int>> &M, 
                    const vector<vector<int>> &times,
                    const Battle &battle)
{
    auto [n_1, v_1, n_2, v_2] = battle;

    int min_x = times[n_1][v_1] - times[n_2][v_2 + 1] + 1;
    int max_x = times[n_1][v_1 + 1] - times[n_2][v_2] - 1;

    M[n_1][n_2] = max(M[n_1][n_2], min_x);
    M[n_2][n_1] = max(M[n_2][n_1], -max_x);
}

bool check_consistency(const vector<vector<int>> &times,
                       const vector<Battle> &battles,
                       const Battle &query)
{
    const int n = times.size();

    vector<vector<int>> M(n, vector<int>(n, numeric_limits<int>::min()));

    for (auto battle : battles) {
        add_constraint(M, times, battle);
    }
    add_constraint(M, times, query);

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                M[i][j] = max(M[i][j], M[i][k] + M[k][j]);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (M[i][i] > 0) {
            return false;
        }
    }

    return true;
}

int main() {
    int n, m, k, q;

    cin >> n;
    vector<vector<int>> times(n);
    for (int i = 0; i < n; i++) {
        cin >> m;
        times[i] = vector<int>(m);
        for (int j = 0; j < m; j++) {
            cin >> times[i][j];
        }
    }

    cin >> k;
    vector<Battle> battles(k);
    for (int i = 0; i < k; i++) {
        cin >> battles[i].nation_1 >> battles[i].monarch_1 
            >> battles[i].nation_2 >> battles[i].monarch_2;
    }

    cin >> q;
    vector<Battle> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].nation_1 >> queries[i].monarch_1
            >> queries[i].nation_2 >> queries[i].monarch_2;
    }

    for (auto query : queries) {
        cout << (check_consistency(times, battles, query) ? "Da" : "Ne") << endl;
    }

    return 0;
}