Submission #1203177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203177		SSKMF	Potemkin cycle (CEOI15_indcyc)	C++20	50 / 100	1095 ms	1488 KiB

indcyc

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

vector <int> adiacenta[1001];
int distanta[1001] , sursa[1001] , __sursa[1001] , stiva[1001];

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

    int numar_noduri , numar_muchii;
    cin >> numar_noduri >> numar_muchii;

    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 inceput = 1 ; inceput <= numar_noduri ; inceput++)
    {
        for (int indice = 1 ; indice <= numar_noduri ; indice++)
            { distanta[indice] = -1; }

        queue <int> candidati;
        distanta[inceput] = 0;
        sursa[inceput] = 0;
        __sursa[inceput] = 0;
        
        for (auto vecin : adiacenta[inceput])
        { 
            __sursa[vecin] = inceput;
            sursa[vecin] = vecin;
            distanta[vecin] = 1;
            candidati.push(vecin); 
        }

        while (!candidati.empty())
        {
            int nod = candidati.front();
            candidati.pop();

            for (auto vecin : adiacenta[nod]) {
                if (distanta[vecin] == -1)
                {
                    __sursa[vecin] = nod;
                    distanta[vecin] = distanta[nod] + 1;
                    sursa[vecin] = sursa[nod];
                    candidati.push(vecin);
                }
                else
                    if (sursa[nod] != sursa[vecin] && distanta[nod] + distanta[vecin] > 2)
                    {
                        bool gasit = false;
                        for (auto __vecin : adiacenta[sursa[nod]]) {
                            if (gasit |= (__vecin == sursa[vecin]))
                                { break; }
                        }

                        if (!gasit)
                        {
                            while (nod != inceput) {
                                cout << nod << ' ';
                                nod = __sursa[nod];
                            }

                            nod = vecin;
                            while (nod) {
                                stiva[++stiva[0]] = nod;
                                nod = __sursa[nod];
                            }

                            while (stiva[0])
                                { cout << stiva[stiva[0]--] << ' '; }

                            return 0;
                        }
                    }
            }
        }
    }

    cout << "no";
    return 0;
}

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