Problem #198

entries

Time limit: 0.15s
Memory limit: 32MB
Input: entries.in
Output: entries.out

Se consideră un graf care inițial este format din P noduri izolate, etichetate de la 1 la P. Se mai consideră N intrari, unde intrare poate însemna:

  • comandă – o comandă are forma I+J, cu semnificația că în graf se adaugă muchia care unește nodurile I și J (dacă I și J erau deja unite în acel moment, nu se întreprinde nici o acțiune);
  • întrebare – o întrebare este de forma I?J, adică se întreabă dacă în acel moment I și J sunt în aceeasi componentă conexă.

Cerință

Se pleacă deci de la un graf inițial format din noduri izolate, care pe parcurs se „unifică”. Tot pe parcurs sunteți întrebat dacă anumite perechi de noduri sunt sau nu în aceeași componentă conexă.

Date de intrare

Din fisierul entries.in veți citi de pe prima linie numărul N de intrari. Pe următoarele N linii se găsesc intrările, câte una pe linie. O intrare este codificată prin trei numere separate prin câte un blanc. Primele două numere reprezintă nodurile I și J (numere întregi, cuprinse între 1 și P), iar al treilea este 1 dacă intrarea este o comandă, respectiv 2 dacă intrarea este o întrebare.

Date de ieșire

La fiecare întrebare, veți scrie pe o linie separată în fișierul entries.out numărul 1 dacă nodurile despre care ați fost întrebat sunt în acel moment în aceeași componentă conexă, respectiv numărul 0 în caz contrar.

Restricții și precizări

  • Pentru 40 de puncte: 1 ≤ N ≤ 5 000, 1 ≤ P ≤ 10 000 000
  • Pentru alte 60 de puncte: 1 ≤ N ≤ 100 000, 1 ≤ P ≤ 500 000 000
  • Problema a fost modificată

Exemplu

entries.in

9
1 2 2
1 2 1
3 7 2
2 3 1
1 3 2
2 4 2
1 4 1
3 4 2
1 7 2

entries.out

0
0
1
0
1
0

General info

Uploader: liviu

Author: Bogdan Dumitru

Source: ONI 2001 XI-XII: Ziua 2 Problema 3 (Modificată)

Submissions