oj.uz

답안 #498144

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
498144 2021-12-24T12:35:58 Z aurims Monthly railway pass (LMIO18_menesinis_bilietas) C++14
0 / 100
 574 ms 31940 KB 
#include <bits/stdc++.h>
#define MAX 500000
#define pb push_back
using namespace std;

/*
input for subtask 1

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

/*
input for subtask 2

4 5
2 1 A
2 3 A
2 4 A
1 3 A
4 3 A
*/

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 suskaiciuoti_laipsnius(int i)
{
    int cnt = 0;
    for(int kaimynas : miestai[i].autikai)
        cnt++;
    return cnt;
}

int main()
{
    int N, M; // N - miestai, M - transp. linijos
    cin >> N >> M;
    miestai.resize(N); // bus tik N miestu
    int subt = -1;
    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);
            subt = 1;
        }
        else if(t == 'A')
        {
            miestai[a-1].autikai.pb(b-1);
            miestai[b-1].autikai.pb(a-1);
            subt = 2;
        }
    }
    // jei egzistuoja tik traukinio linijos tai:
    // a) is bet kurio miesto bus galima pasiekt bet kuri ir Marius gales apsistot bet kokiam mieste
    // b) kur nors truks linijos ir tada Marius negales apsistot nei vienam mieste
    if(subt == 1)
    {
        paieska_gilyn(0);
        for(int i = 0; i < N; i++)
            if(!miestai[i].aplankytas)
            {
                cout << 0;
                return 0;
            }
        cout << N;
        return 0;   
    }
    else if(subt == 2)
    {
        int ans = 0;
        for(int i = 0; i < N; i++)
        {
            if(suskaiciuoti_laipsnius(i) == N-1) // jei gali aplankyt visus kitus miestus (isskyrus save)
                ans++;
        }
        cout << ans;
    }
}

Compilation message

menesinis_bilietas.cpp: In function 'int suskaiciuoti_laipsnius(int)':
menesinis_bilietas.cpp:51:13: warning: unused variable 'kaimynas' [-Wunused-variable]
   51 |     for(int kaimynas : miestai[i].autikai)
      |             ^~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 574 ms 31940 KB Output is correct
2 Correct 0 ms 292 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Incorrect 15 ms 26004 KB Output isn't correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 26004 KB Output isn't correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 292 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 272 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 272 KB Output isn't correct
2 Halted 0 ms 0 KB -