157112025-02-23 15:05:12SRobKerékpártúra (50 pont)cpp17Wrong answer 46/50118ms2356 KiB
// kerekparTura_NT_kat2_ford2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> graf;
vector<int> mikorVoltunkItt; /*a: 1.
                               b: 2.*/
vector<bool> jok; // megoldásként jó, tehát pl az ábrán az 1-es csúcs. Nem elérhető, de jó megoldás
vector<bool> elerheto; // elérhető és jó megoldás is ezáltal
int Kkezdo;
void DFS(int csucs, int lepes)
{
    int szomszed;
    mikorVoltunkItt[csucs] = lepes;
    for (int i = 0; i < graf[csucs].size(); i++)
    {
        szomszed = graf[csucs][i];
        if (mikorVoltunkItt[szomszed] == -1)
        {
            DFS(szomszed, lepes + 1);
        }
        else if (mikorVoltunkItt[szomszed] != -1 &&
                 elerheto[szomszed] &&
                 mikorVoltunkItt[szomszed] != lepes-1)
        {
            elerheto[csucs] = true;
        }
    }

    for (int i = 0; i < graf[csucs].size(); i++)
    {
        szomszed = graf[csucs][i];
        if (elerheto[szomszed])
        {
            elerheto[csucs] = true;
        }
    }
    if (elerheto[csucs])
    {
        for (int i = 0; i < graf[csucs].size(); i++)
        {
            if (graf[csucs][i] != Kkezdo)
            {
                jok[graf[csucs][i]] = true;
            }
            
        }
    }
}
int main()
{
#pragma region beolvasás



    int Ncsucs, Mel;
    cin >> Ncsucs >> Mel >> Kkezdo;
    graf.resize(Ncsucs+1); // 0. csucsot nem veszem figyelembe
                            // azt adja meg, hogy belőle hova lehet menni
    mikorVoltunkItt.resize(Ncsucs + 1);
    jok.resize(Ncsucs + 1);
    elerheto.resize(Ncsucs + 1);
    int seged1, seged2;
    for (int i = 0; i < Mel; i++)
    {
        cin >> seged1 >> seged2;
        graf[seged1].push_back(seged2);

    }
   /* for (int i = 0; i < graf.size(); i++)
    {
        cout << i  << ".: ";
        for (int j = 0; j < graf[i].size(); j++)
        {
            cout << graf[i][j] << " ";
        }
        cout << endl;
    }*/
#pragma endregion

#pragma region elokeszulet



    for (int i = 1; i <= Ncsucs; i++)
    {
        mikorVoltunkItt[i] = -1;
        jok[i] = false;
        elerheto[i] = false;
    }

    elerheto[Kkezdo] = true;
    DFS(Kkezdo, 1);
    //cout << "jok: " << endl;
    int joDb = 0;
    for (int i = 1; i <= Ncsucs; i++)
    {
        if (jok[i])
        {
            joDb++;
        }
    }
    if (joDb > 0)
    {
        cout << joDb << endl;
        for (int i = 1; i <= Ncsucs; i++)
        {
            if (jok[i])
            {
                cout << i << " ";
            }
        }
    }
    else
    {
        cout << "0";
    }
    
#pragma endregion
}
SubtaskSumTestVerdictTimeMemory
base46/50
1Accepted0/01ms508 KiB
2Accepted0/018ms1076 KiB
3Wrong answer0/21ms316 KiB
4Accepted2/21ms316 KiB
5Accepted2/21ms316 KiB
6Accepted2/21ms316 KiB
7Accepted2/21ms380 KiB
8Accepted2/22ms316 KiB
9Wrong answer0/23ms316 KiB
10Accepted2/23ms316 KiB
11Accepted2/24ms556 KiB
12Accepted2/210ms504 KiB
13Accepted2/29ms532 KiB
14Accepted2/218ms508 KiB
15Accepted3/330ms1624 KiB
16Accepted4/434ms1836 KiB
17Accepted4/448ms1844 KiB
18Accepted3/343ms1784 KiB
19Accepted3/335ms1812 KiB
20Accepted3/3105ms2356 KiB
21Accepted3/3118ms2356 KiB
22Accepted3/3118ms2356 KiB