Fişierul intrare/ieşire:disconnect.in, disconnect.outSursăAlgoritmiada 2015, Runda 1
AutorAdrian VladuAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test1.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Disconnect

Fie T un arbore neorientat cu N noduri. Vom aplica asupra lui M operaţii de tipul:

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.

Date de intrare

Fişierul de intrare disconnect.in va conţine pe prima linie numerele N şi M, semnificând numărul de noduri, respectiv numărul de operaţii care se vor efectua asupra arborelui. Următoarele N - 1 linii conţin câte o pereche de numere X Y, semnificând faptul că există o muchie neorientată între nodurile X şi Y. Următoarele M linii conţin câte trei numere tip X Y. Numărul tip denotă tipul operaţiei, fiind egal cu 1 dacă este vorba de o ştergere sau 2 dacă e vorba de o întrebare. Numerele X şi Y vor fi folosite pentru a genera nodurile pe care se va aplica operaţia respectivă. Mai exact, aceste noduri vor fi A = X xor V şi B = X xor V unde V este o variabila iniţial egală cu 0. După fiecare operaţie de tip 2 variabila V îşi va schimba valoarea în A (dacă răspunsul la întrebare a fost pozitiv), respectiv în B (dacă acesta a fost negativ). Vă oferim un fragment de cod în C++ care generează şi rezolvă operaţiile.

int V = 0;

    for (int i = 0; i < M; ++i) {
        int type, x, y; cin >> type >> x >> y;

        int a = x xor V;
        int b = y xor V;

        if (type == 1) {
            removeEdge(a, b);
        } else
            if (query(a, b)) {
                cout << "YES\n";
                V = a;
            } else {
                cout << "NO\n";
                V = b;
            }
    }

Date de ieşire

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.

Restricţii şi precizări

  • 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. 

Exemplu

disconnect.indisconnect.out
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

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?