oj.uz

Submission #498524

# Submission time Handle Problem Language Result Execution time Memory
498524 2021-12-25T11:34:52 Z aurims Monthly railway pass (LMIO18_menesinis_bilietas) C++14
100 / 100
 906 ms 43228 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 40912 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 643 ms 29728 KB Output is correct
5 Correct 2 ms 1064 KB Output is correct
6 Correct 120 ms 5828 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 29728 KB Output is correct
2 Correct 2 ms 1064 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 4 ms 436 KB Output is correct
6 Correct 241 ms 10372 KB Output is correct
7 Correct 906 ms 43228 KB Output is correct
8 Correct 14 ms 1828 KB Output is correct
9 Correct 23 ms 2072 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 4 ms 436 KB Output is correct
6 Correct 1 ms 272 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 3 ms 428 KB Output is correct
10 Correct 6 ms 460 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 6 ms 588 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 3 ms 400 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 352 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 272 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 428 KB Output is correct
5 Correct 6 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 6 ms 588 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 3 ms 400 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 352 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 296 KB Output is correct
20 Correct 4 ms 436 KB Output is correct
21 Correct 2 ms 1064 KB Output is correct
22 Correct 14 ms 1828 KB Output is correct
23 Correct 23 ms 2072 KB Output is correct
24 Correct 120 ms 5828 KB Output is correct
25 Correct 17 ms 1024 KB Output is correct
26 Correct 234 ms 9552 KB Output is correct
27 Correct 86 ms 3864 KB Output is correct
28 Correct 102 ms 5012 KB Output is correct
29 Correct 60 ms 2992 KB Output is correct
30 Correct 118 ms 5956 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 272 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 428 KB Output is correct
5 Correct 6 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 6 ms 588 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 3 ms 400 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 352 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 17 ms 1024 KB Output is correct
17 Correct 234 ms 9552 KB Output is correct
18 Correct 86 ms 3864 KB Output is correct
19 Correct 102 ms 5012 KB Output is correct
20 Correct 60 ms 2992 KB Output is correct
21 Correct 118 ms 5956 KB Output is correct
22 Correct 604 ms 40912 KB Output is correct
23 Correct 0 ms 204 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 643 ms 29728 KB Output is correct
26 Correct 0 ms 204 KB Output is correct
27 Correct 1 ms 296 KB Output is correct
28 Correct 4 ms 436 KB Output is correct
29 Correct 2 ms 1064 KB Output is correct
30 Correct 241 ms 10372 KB Output is correct
31 Correct 906 ms 43228 KB Output is correct
32 Correct 14 ms 1828 KB Output is correct
33 Correct 23 ms 2072 KB Output is correct
34 Correct 120 ms 5828 KB Output is correct
35 Correct 52 ms 4588 KB Output is correct
36 Correct 451 ms 17652 KB Output is correct
37 Correct 287 ms 22468 KB Output is correct