Submission #498524

#	Time	Username	Problem	Language	Result	Execution time	Memory
498524		aurims	Monthly railway pass (LMIO18_menesinis_bilietas)	C++14	100 / 100	906 ms	43228 KiB

menesinis_bilietas

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

struct miestas{
    bool aplankytas;
    vector<int> autikai;    // kokius miestus gali pasiekt autiku
    vector<int> traukiniai; // kokius miestus gali pasiekt traukiniu
    int grupe; // kokiam jungumo komponentui priklauso

    miestas() : aplankytas(false), grupe(-1) {}
};
vector<miestas> miestai;

// visus miestus, kurie pasiekiami is i-tojo miesto traukiniu priskiriam gr grupe
void priskirk_grupe(int i, int gr) // realiai dfs + spalvinimo algoritmas is https://inf-knyga.nmakademija.lt/lt/latest/07_grafų_pagrindai.html#paieska-gilyn
{
    miestai[i].grupe = gr;
    for(int kaimynas : miestai[i].traukiniai)
    {
        if(miestai[kaimynas].grupe != -1) // jeigu kaimynas priklauso kitam jungumo komponentui
            continue;
        priskirk_grupe(kaimynas, gr); // einam lankyt kaimyno kaimynu
    }
}

int rask_gretimas_komp(int i, vector<bool>& ak)
{
    miestai[i].aplankytas = true;
    int dydis = 1;

    // aplankom visas i-tojo miesto kaimynu komponentes vienu autiku
    for(int idx : miestai[i].autikai)
    {
        ak[miestai[idx].grupe] = true;
    }

    for(int idx : miestai[i].traukiniai)
    {
        if(miestai[idx].aplankytas)
            continue;
        
        dydis += rask_gretimas_komp(idx, ak);
    }

    return dydis;
}

// jei is i-tojo miesto galim pasiekt 
int rask_bendros_komp_miestu_sk(int i, int grsk)
{
    vector<bool> ak(grsk, false); // aplankyti komponentai
    ak[miestai[i].grupe] = true; // nes save galim aplankyt

    int ans = rask_gretimas_komp(i, ak);

    for(int i = 0; i < grsk; i++)
    {
        if(ak[i] == false) // jeigu yra neaplankytu komponentu
            return 0;      // tai mes is miesto i negalim pasiekt visu kitu miestu
    }

    return ans;
}

int main()
{
    int N, M; // N - miestai, M - transp. linijos
    cin >> N >> M;
    miestai.resize(N); // bus tik N miestu
    for(int i = 0; i < M; i++)
    {
        int a, b;
        char t;
        cin >> a >> b >> t;
        if(t == 'T')
        {
            miestai[a-1].traukiniai.pb(b-1); // sitose eilutese is indekso ir pb args atemam 1, nes miestai sunumeruoti 1 -> N, o vektoriaus indeksai 0 -> N-1
            miestai[b-1].traukiniai.pb(a-1);
        }
        else if(t == 'A')
        {
            miestai[a-1].autikai.pb(b-1);
            miestai[b-1].autikai.pb(a-1);
        }
    }
    // suskirstom miestus i jungumo komponentu grupes
    int grupe = 0;
    for(int i = 0; i < N; i++)
    {
        if(miestai[i].grupe == -1)
        {
            priskirk_grupe(i, grupe);
            grupe++;
        }
    }

    //
    int ans = 0;
    for(int i = 0; i < N; i++)
    {
        if(!miestai[i].aplankytas)
            ans += rask_bendros_komp_miestu_sk(i, grupe);
    }
    cout << ans;
    return 0;   
}

• Subtask 1: 10 / 10
• Subtask 2: 6 / 6
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35
• Subtask 5: 19 / 19