제출 #498137

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
498137		aurims	Monthly railway pass (LMIO18_menesinis_bilietas)	C++14	10 / 100	603 ms	38508 KiB

menesinis_bilietas

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

/*
input

6 5
1 2 T
2 3 T
2 4 T
5 6 T
4 6 T
*/

struct miestas{
    bool aplankytas;
    vector<int> autikai;
    vector<int> traukiniai;

    miestas() : aplankytas(false) {}
};
vector<miestas> miestai;

void paieska_gilyn(int i)
{
    miestai[i].aplankytas = true; // nes visad save aplankom
    for(int kaimynas : miestai[i].traukiniai)
    {
        if(miestai[kaimynas].aplankytas) // jeigu aplankytas jau, tai skipinam
            continue;
        paieska_gilyn(kaimynas); // einam lankyt kaimyno kaimynu
    }
}

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);
        }
    }
    paieska_gilyn(0);
    for(int i = 0; i < N; i++)
        if(!miestai[i].aplankytas)
        {
            cout << 0;
            return 0;
        }
    cout << N;
    return 0;   
}

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