제출 #1278845

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278845		SSKMF	Colors (RMI18_colors)	C++20	100 / 100	494 ms	53544 KiB

colors

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

int reprezentant[150001] , grad[150001] , minim[150001];
stack < pair < pair < pair <int , int&> , pair <int , int&> > , int& > > operatii;
vector <int> adiacenta[150001] , adaugat[300000] , dorit[150001];
pair <int , int> interval[150001];
bool gasit , activ[150001];

inline void Update (const int nod , const int stanga , const int dreapta , const int indice)
{
    if (interval[indice].second < stanga || dreapta < interval[indice].first)
        { return; }

    if (interval[indice].first <= stanga && dreapta <= interval[indice].second)
        { adaugat[nod].push_back(indice); return; }

    const int mijloc = (stanga + dreapta) >> 1;
    Update(nod + 1 , stanga , mijloc , indice);
    Update(nod + ((mijloc - stanga + 1) << 1) , mijloc + 1 , dreapta , indice);
}

inline void Rollback ()
{
    operatii.top().second = 0;
    operatii.top().first.first.second = operatii.top().first.first.first;
    operatii.top().first.second.second = operatii.top().first.second.first;
    operatii.pop();
}

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

inline bool Unire (int nod_1 , int nod_2)
{
    if ((nod_1 = Radacina(nod_1)) == (nod_2 = Radacina(nod_2)))
        { return false; }
        
    if (grad[nod_1] < grad[nod_2])
        { swap(nod_1 , nod_2); }

    operatii.push({{{minim[nod_1] , minim[nod_1]} , {grad[nod_1] , grad[nod_1]}} , reprezentant[nod_2]});

    reprezentant[nod_2] = nod_1;
    grad[nod_1] += (grad[nod_1] == grad[nod_2] ? 1 : 0);
    minim[nod_1] = min(minim[nod_1] , minim[nod_2]);
    return true;
}

inline void Parcurgere (const int nod , const int stanga , const int dreapta)
{
    int ramas = 0;
    for (auto& __nod : adaugat[nod])
    {
        activ[__nod] = true;
        for (auto& vecin : adiacenta[__nod]) {
            if (activ[vecin])
                { ramas += Unire(__nod , vecin); }
        }
    }
    
    if (stanga == dreapta)
    {
        for (auto& __nod : dorit[stanga]) {
            if (minim[Radacina(__nod)] != stanga)
                { gasit = true; }
        }

        dorit[stanga].clear();
    }
    else
    {
        const int mijloc = (stanga + dreapta) >> 1;
        Parcurgere(nod + 1 , stanga , mijloc);
        Parcurgere(nod + ((mijloc - stanga + 1) << 1) , mijloc + 1 , dreapta);
    }

    for (auto& __nod : adaugat[nod])
        { activ[__nod] = false; }

    adaugat[nod].clear();
    while (ramas--)
        { Rollback(); }
}

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

    for (int indice = 1 ; indice <= numar_noduri ; indice++)
        { cin >> interval[indice].second; minim[indice] = interval[indice].second; }

    gasit = false;
    for (int indice = 1 ; indice <= numar_noduri ; indice++)
        { cin >> interval[indice].first; gasit |= (interval[indice].first > interval[indice].second); }

    if (!gasit)
    {
        while (numar_muchii--)
        {
            int nod[2]; cin >> nod[0] >> nod[1];
            adiacenta[nod[0]].push_back(nod[1]);
            adiacenta[nod[1]].push_back(nod[0]);
        }

        for (int indice = 1 ; indice <= numar_noduri ; indice++)
            { Update(1 , 1 , numar_noduri , indice); dorit[interval[indice].first].push_back(indice); }

        Parcurgere(1 , 1 , numar_noduri);

        for (int indice = 1 ; indice <= numar_noduri ; indice++)
            { adiacenta[indice].clear(); }
    }
    else
    {
        while (numar_muchii--)
            { int nod[2]; cin >> nod[0] >> nod[1]; }
    }

    cout << (gasit ? "0\n" : "1\n");
}

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

    int numar_teste;
    cin >> numar_teste;
    while (numar_teste--)
        { Solve(); }
    
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 10 / 10
• Subtask 8: 22 / 22