Zadanie Architekt, find and union

Mam takie zadanie:

Jaś jest początkującym architektem i postanowił zaprojektować swoje własne miasto!Całymi dniami siedzi przy stole kreślarskim i ustala, jak wysokie powinny być poszcze-gólne budynki. Póki co projekt Jasia zawiera jedynie wytyczne w postaci „Budynek nripowinien być dokładniewmetrów wyższy niż budynek nrj”. Mama chłopca zauważyła,że nie wszystkie te warunki mogą zostać spełnione. Postanowiła przeczytać jego zapi-ski i usuwać te, których realizacja nie byłaby możliwa. Powiedz, które zdania zostanąskreślone, a które ten los ominie

Wejście
W pierwszym wierszu wejścia znajdują się liczby N i Z(2 <= N <= 10^5,1 <= Z <= 10^5), oznaczające liczbębudynków w projektowanym mieście i liczbę zdań zapisanych przez Jasia. W kolejnychZwierszach znajdująsię opisy pomysłów chłopca. Opis pomysłu składa się z trzech liczbi,jiw(1 <= i, j <= N,i <= j ,0 <= w <= 10^4),oznaczających, że budynek nri ma być dokładniewmetrów wyższy, niż budynek nrj.

Wyjście
Dla każdego zdania, jeśli jest spełnialne w świetle poprzednich zaakceptowanych pomysłów, wypisz TAK, wprzeciwnym wypadku wypisz NIE i nie bierz go pod uwagę przy ocenie spełnialności kolejnych.

Wejście:
4 6
2 1 2
3 1 1
2 3 1
4 2 0
4 3 2
4 1 2

Wyjście:
TAK
TAK
TAK
TAK
NIE
TAK

No i miałem pomysł żeby robić find and union tzn jak np. mamy 1 2 3:
to 2 dajemy reprezentanta 1 i w osobnej tablicy będziemy trzymać sumaryczną wysokość (czyli indeks 1 zmieniamy na 3)

No i teraz jeżeli chcemy sprawdzić czy można robić zależność sprawdzamy czy wartość reprezentana pierwszej liczby jest <= wartości reprezentanta drugiej liczby, wszystko wyglądało dobrze ale np dla danych:

2 1 1
3 2 1
3 1 0
Wyjście będzie wynosić:
TAK
TAK
NIE

A powinno być:
TAK
TAK
TAK

proszę o pomoc :)

A kod który ci nie działa gdzie?

@Suchy702: nie rozumiem Twojego pomysłu na rozwiązanie.

Mnie się wydaje, że tu by pasowała rekurencja.

PS: Tzn. nie tyle rekurencja, co jedna funkcja, ale rekurencją ja bym to zrobił. ;) Może być też zwykła pętla.

Niepotrzebne są joiny. Całość zadania robi się prostsza jeśli zauważysz, że:

• budynek nr. 1 jest zawsze wysoki na nie wiadomo ile, ale to nie ma znaczenia
• potrzebne są tobie dwie wartości specjalne - tj. wysokość referencyjna (np. 0) oraz niezdefiniowana (np. -1)

I teraz:

1. Na początku tworzysz sobie "plan" miasta, tj. tworzysz listę budynków od 1 do N. Pierwszemu budynkowi ustawiasz wysokość referencyjną. Wszystkim innym budynkom dajesz wysokość niezdefiniowaną.
2. Jednocześnie tworzysz tablicę wyników. Może to być tablica int[], gdzie -1 - fałsz, 0 - jeszcze nie testowano, 1 - prawda. Wypełniasz ją zerami na start.
3. Teraz wczytujesz listę pomysłów Jasia do jakiejś kolekcji.
4. Iterujesz po liście pomysłów Jasia. Tutaj opis nomenklatury:
   dla linijki J I W:
   "2 1 1"

Będę używał słownictwa:
Budynek wybrany: budynek #2
Budynek referencyjny: budynek #1
Wysokość budynku: wysokość budynku #2 (na starcie nie jest znane)
Wysokość względna: 1
Wysokość referencyjna: wysokość budynku referencyjnego (tutaj: wysokość budynku #1)

5. Iterujesz po liście.
6. Teraz masz trzy przypadki:
   6.1. Wysokość referencyjna budynku jest niezdefiniowana - wtedy ignorujesz .
   6.2. Wysokość referencyjna jest zdefiniowana, natomiast wysokość budynku jest już niezdefiniowana - wtedy wyliczasz wysokość budynku i zapisujesz PRAWDA w tablicy wyników.
   6.3. Wysokość referencyjna oraz wysokość budynku jest znana - wtedy sprawdzasz, czy wysokość budynku jest sumie wysokości referencyjnej i względnej, a wynik porównania zapisujesz w tablicy wyników.
7. Iterujesz po liście, aż do skutku - tzn. aż nie przeliczysz wszystkich wyników.

Jest to najprostszy sposób, który dałoby się potem usprawnić (np. można by wykonać tylko jedną iterację odpowiednio sortując pomysły) - ale nie chcę tutaj dawać gotowego rozwiązania.

@Silv no tak na chłopski rozum to można by tez zbudować z tego wyrażenie logiczne i sprawdzać czy nadal jest prawdziwe po dodaniu nowego warunku ;)
Ja myśle że ten pomysł z union-find nie jest taki zły. Nie rozumiem trochę twojego przykładu, bo twój wynik jest ok.
2 1 1 -> 2 wyższy od 1 o 1
3 2 1 -> 3 wyższy od 2 o 1 (czyli wyższy od 1 o 2)
3 1 0 -> 3 wyższy od 1 o 0, czyli błąd

Okej mam rozwiązanie, trzeba było znać/zauważyć pewnien trick. Robimy Find and Union, ale trzymamy wszystkie dzieci jednego rodzica, do tego robimy tablicę reprezentującą wysokości budynków. Teraz przy każdej zależności będziemy przerzucać wszystkie dzieci ojca który ma ich mniej, do tego który ma ich więcej i to będzie działać w złożonośći O(n*logn) (nie O(n^2 ) ;]), aktualizując wysokości budynków. Jeśli łączymy grupy to wiadomo że odpowiedź jest "TAK", jeśli Jaś chce zrobić zależność dla dwóch budynków w tej samej grupie to sprawdzamy czy ta zależność jest spełniona. kod na 100pkt wygląda tak:

#include <bits/stdc++.h>

using namespace std;

class FindAndUnion{
public:
    vector<int> parent;
    vector<int> amount;
    vector<vector<int>> childs;
    vector<long long> high;

    FindAndUnion(int size){
        parent.resize(size);
        amount.resize(size, 1);
        childs.resize(size);
        high.resize(size);

        for (int i = 0; i < size; i++){
            parent[i] = i;
            childs[i].push_back(i);
        }
    }

    int Find(int x){
        if (parent[x] != x)
            parent[x] = Find(parent[x]);
        return parent[x];
    }

    void change_child(vector<int> & a_childs, vector<int> & b_childs, int change){
        b_childs.push_back(a_childs[a_childs.size() - 1]);
        high[a_childs[a_childs.size() - 1]] -= change;
        a_childs.pop_back();

    }

    bool Union(int i, int j, int w){
        int parent_i = Find(i), parent_j = Find(j);
        if (parent_i == parent_j)
            return high[i] - high[j] == w;
        
        if (amount[parent_i] >= amount[parent_j]){
            int change = high[j] - (high[i] - w); // y = x - w
            while (childs[parent_j].size() > 0){
                change_child(childs[parent_j], childs[parent_i], change);
            }
            parent[parent_j] = parent_i;
            amount[parent_i] += amount[parent_j];
        }
        else{
            int change = high[i] - (high[j] + w); // x = y + w
            while (childs[parent_i].size() > 0){
                change_child(childs[parent_i], childs[parent_j], change);
            }
            parent[parent_i] = parent_j;
            amount[parent_j] += amount[parent_i];
        }

        return true;
    }
};


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, z;
    cin >> n >> z;
    FindAndUnion f_and_u(n + 1);

    int i, j, w;
    for (int t = 0; t < z; t++){
        cin >> i >> j >> w;
        if (f_and_u.Union(i, j, w))
            cout << "TAK\n";
        else 
            cout << "NIE\n";
    }

    return 0;
}

@Suchy702: w jaki sposób wyszła Ci złożoność n*log n? Standardowa implementacja ma coś znacznie bliższego n. Polecam jako ćwiczenie analizę, czy gdziekolwiek osiągasz to n*log n, czy jednak przeszacowałeś.