Submission #498524

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
498524	2021-12-25 11:34:52	aurims	Monthly railway pass (LMIO18_menesinis_bilietas)	C++14	100 / 100	906 ms	43228 KiB

menesinis_bilietas

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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