Submission #1290017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290017		SSKMF	Pictionary (COCI18_pictionary)	C++20	14 / 140	1596 ms	3940 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;

struct Intrebare {
    int nod_1 , nod_2 , stanga , dreapta , indice;
} intrebare[100001];

int reprezentant[100001] , grad[100001] , rezultat[100001];

inline int Radacina (const int nod)
{
    return reprezentant[nod] ? (reprezentant[nod] = Radacina(reprezentant[nod])) : nod;
}

inline void Unire (int nod_1 , int nod_2)
{
    if ((nod_1 = Radacina(nod_1)) == (nod_2 = Radacina(nod_2)))
        { return; }

    if (grad[nod_1] < grad[nod_2])
        { swap(nod_1 , nod_2); }

    grad[nod_1] += (grad[nod_1] == grad[nod_2] ? 1 : 0);
    reprezentant[nod_2] = nod_1;
}

inline void Solve ()
{
    int numar_noduri , limita , numar_intrebari;
    cin >> numar_noduri >> limita >> numar_intrebari;

    for (int indice = 1 ; indice <= numar_intrebari ; indice++)
    {
        cin >> intrebare[indice].nod_1 >> intrebare[indice].nod_2;

        if (intrebare[indice].nod_1 > intrebare[indice].nod_2)
            { swap(intrebare[indice].nod_1 , intrebare[indice].nod_2); }

        intrebare[indice].stanga = 1;
        intrebare[indice].dreapta = intrebare[indice].nod_1;
        intrebare[indice].indice = indice;
    }

    int ramas = numar_intrebari;
    for (int indice = numar_intrebari ; indice ; indice--) {
        if (intrebare[indice].nod_1 == intrebare[indice].nod_2)
        { 
            intrebare[indice].dreapta = limita + 1;
            swap(intrebare[indice] , intrebare[ramas--]);
        }
    }

    int cnt = 0;
    while (ramas)
    {
        if (++cnt == 21)
            { exit(-1); }

        sort(intrebare + 1 , intrebare + ramas + 1 , [] (Intrebare& optiune_1 , Intrebare& optiune_2) -> bool {
            return optiune_1.stanga + optiune_1.dreapta > optiune_2.stanga + optiune_2.dreapta;
        });

        for (int indice = limita , __indice = 1 ; __indice <= ramas ; indice--)
        {
            for (int candidat = (indice << 1) ; candidat <= numar_noduri ; candidat += indice)
                { Unire(indice , candidat); }

            while (__indice <= ramas && (intrebare[__indice].stanga + intrebare[__indice].dreapta) / 2 == indice) {
                if (Radacina(intrebare[__indice].nod_1) == Radacina(intrebare[__indice].nod_2)) { intrebare[__indice].stanga = indice + 1; }
                else { intrebare[__indice].dreapta = indice - 1; }
                __indice++;
            }
        }

        for (int indice = 1 ; indice <= numar_noduri ; indice++)
            { reprezentant[indice] = grad[indice] = 0; }

        int __ramas = 0;
        for (int indice = 1 ; indice <= ramas ; indice++) {
            if (intrebare[indice].stanga <= intrebare[indice].dreapta)
                { swap(intrebare[++__ramas] , intrebare[indice]); }
        }

        ramas = __ramas;
    }

    for (int indice = 1 ; indice <= numar_intrebari ; indice++)
        { rezultat[intrebare[indice].indice] = limita - intrebare[indice].dreapta + 1; }

    for (int indice = 1 ; indice <= numar_intrebari ; indice++)
        { cout << rezultat[indice] << '\n'; }
}

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int numar_teste = 1;
    // cin >> numar_teste;
    while (numar_teste--)
        { Solve(); }

    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14