Diferente pentru problema/disconnect intre reviziile #19 si #30
Nu exista diferente intre titluri.
Diferente intre continut:
Fie $T$ un arbore neorientat cu $N$ noduri. Vom aplica asupra lui $M$ operaţii de tipul:
$1 x y$ Sesterge muchia $x-y$ din arbore. $2 x y$ Se puneintrebarea "Existadrum in arbore de la nodul $x$ la nodul $y$?"
$1 x y$ Se şterge muchia $x-y$ din arbore. $2 x y$ Se pune întrebarea "Există drum in arbore de la nodul $x$ la nodul $y$?"
Cerinţa este ca programul vostru să afişeze răspunsul corect pentru toate operaţiile de tip $2$.
for (int i = 0; i < M; ++i) { int type, x, y; cin >> type >> x >> y;
int a = x^V; int b = y^V;
int a = x xor V; int b = y xor V;
if (type == 1) {
T.removeEdge(a, b);
removeEdge(a, b);
} else
if (T.query(a, b)) {
if (query(a, b)) {
cout << "YES\n"; V = a; } else {
Fişierul de ieşire $disconnect.out$ va conţine câte o linie pentru fiecare operaţie de tip $2$. Linia va conţine $YES$ dacă răspunsul este pozitiv şi $NO$ altfel.
h2. Restricţii
h2. Restricţii şi precizări
* $1 ≤ N ≤200 000$
* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 500 000$ * Pentru $20%$ din punctaj testele respectă restricţia $1 ≤ N ≤ 1 000$, $1 ≤ M ≤ 5 000$ * Pentru $40%$ din punctaj testele respectă restricţia $1 ≤ N ≤ 10 000$, $1 ≤ M ≤ 500 000$
* Operaţia $xor$ poate fi implementată prin operatorul "^" sau "xor" în C/C++ şi operatorul "xor" în Pascal.
h2. Exemplu table(example). |_. disconnect.in |_. disconnect.out |
| This is some text written on multiple lines. | This is another text written on multiple lines.
| 6 7 1 2 1 3 1 4 4 5 4 6 2 2 5 1 3 6 2 0 7 2 7 6 2 7 4 1 4 7 2 6 7 | YES NO YES YES NO
| h3. Explicaţie
...
Odată generate operaţiile ar arăta în felul următor: 2 2 5 1 1 4 2 2 5 2 2 3 2 5 6 1 1 2 2 3 2
== include(page="template/taskfooter" task_id="disconnect") ==