Submission #498242

#TimeUsernameProblemLanguageResultExecution timeMemory
498242aurimsMonthly railway pass (LMIO18_menesinis_bilietas)C++14
100 / 100
721 ms40096 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cassert> using namespace std; struct vertex { int group; // kokiai jungumo komponenciu grupei priklauso vector<int> train_edges; // su kokiais miestais turi traukini vector<int> bus_edges; // su kokiais miestais turi autika bool visited; // ar aplankyta vertex(): group(-1), visited(false) {} // by default, neaplankyta ir nepriklauso jokiai jung. komp. grupei }; vector<vertex> map; // visas virsunes jungumo komponenteje priskiriam vienai grupei void paint_graph(int idx, int colour) { assert(map[idx].group == -1); vertex& v = map[idx]; v.group = colour; // priskiriam miesta prie grupes for (const int& sidx : v.train_edges) { assert(0 <= sidx && sidx < map.size()); vertex& sibling = map[sidx]; if (sibling.group != -1) // jei kaimynas turi grupe, tai skipinam ji continue; paint_graph(sidx, colour); // nuspalvinam kaimyna } } int find_adjacent_comps(int idx, vector<bool>& adjacent) { assert(!map[idx].visited); vertex& v = map[idx]; v.visited = true; int size = 1; for (const int& sidx : v.bus_edges) { assert(0 <= sidx && sidx < map.size()); vertex& sibling = map[sidx]; adjacent[sibling.group] = true; } for (const int& sidx : v.train_edges) { assert(0 <= sidx && sidx < map.size()); vertex& sibling = map[sidx]; if (sibling.visited) continue; size += find_adjacent_comps(sidx, adjacent); } return size; } int find_full_comp_size(int idx, int groups) { vector<bool> bitset(groups, false); // jungumo komponenciu aplankymo sarasas bitset[map[idx].group] = true; // Always visit yourself int size = find_adjacent_comps(idx, bitset); for (int i = 0; i < groups; i++) if (!bitset[i]) // jei yra neaplankyta jungumo komponente, tai vadinasi is miesto map[idx] neina aplankyt visu miestu pigiai return 0; return size; } int main(int argc, const char * argv[]) { ios::sync_with_stdio(false), cin.tie(0); int n, m; cin >> n >> m; map.resize(n); for (int i = 0; i < m; i++) { // iteruojam per transporto linijas int a, b; char c; cin >> a >> b >> c; if (c == 'T') { // jei jungia traukinys // grafe sujungiam tas dvi virsunes map[a-1].train_edges.push_back(b-1); map[b-1].train_edges.push_back(a-1); } else { // jei jungia autikas // grafe sujungiam tas dvi virsunes map[a-1].bus_edges.push_back(b-1); map[b-1].bus_edges.push_back(a-1); } } int group = 0; for (int i = 0; i < n; i++) // iteruojam per miestus if (map[i].group == -1) // jeigu tas miestas dar nepriklauso jokiai grupei paint_graph(i, group++); // tai priskiriam ji kokiai grupei int size = 0; for (int i = 0; i < n; i++) if (!map[i].visited) size += find_full_comp_size(i, group); cout << size << endl; return 0; }

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from menesinis_bilietas.cpp:4:
menesinis_bilietas.cpp: In function 'void paint_graph(int, int)':
menesinis_bilietas.cpp:26:34: warning: comparison of integer expressions of different signedness: 'const int' and 'std::vector<vertex>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         assert(0 <= sidx && sidx < map.size());
      |                             ~~~~~^~~~~~~~~~~~
menesinis_bilietas.cpp: In function 'int find_adjacent_comps(int, std::vector<bool>&)':
menesinis_bilietas.cpp:45:34: warning: comparison of integer expressions of different signedness: 'const int' and 'std::vector<vertex>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         assert(0 <= sidx && sidx < map.size());
      |                             ~~~~~^~~~~~~~~~~~
menesinis_bilietas.cpp:52:34: warning: comparison of integer expressions of different signedness: 'const int' and 'std::vector<vertex>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         assert(0 <= sidx && sidx < map.size());
      |                             ~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...