제출 #1203181

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1203181		SSKMF	Potemkin cycle (CEOI15_indcyc)	C++20	50 / 100	1096 ms	5932 KiB

indcyc

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

vector <int> adiacenta[1001];
set < pair <int , int> > muchii;
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]);
        muchii.insert({min(nod[0] , nod[1]) , max(nod[0] , nod[1])});
    }
    
    for (int inceput = 1 ; inceput <= numar_noduri ; inceput++)
    {
        for (int indice = 1 ; indice <= numar_noduri ; indice++)
            { distanta[indice] = -1; }

        queue <int> candidati;
        distanta[inceput] = sursa[inceput] = __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 && muchii.find({min(sursa[nod] , sursa[vecin]) , max(sursa[nod] , sursa[vecin])}) == muchii.end())
                    {
                        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