fork download
copy 
  1. /*https://p...content-available-to-author-only...j.com/problems/TFIBRE/
  2. Hashmap -> kluczem jest adres w formacie uint, wartosc to vector/lista do jakich adresow (przed hashem) jest polaczony ten wierzcholek grafu.
  3. */
  4. #include <iostream>     //std::cin & std::cout
  5. #include <vector>
  6. #include <queue>
  7. #include <unordered_map>
  8.  
  9. using HashMap = std::unordered_map<uint_fast32_t, std::vector<uint_fast32_t> >;
  10. bool test{0};
  11.  
  12. void Add(HashMap& Connections, uint_fast32_t add1, uint_fast32_t add2)
  13. {
  14.     if (add1==add2)
  15.     {
  16.         Connections[add1];
  17.     }
  18.     else
  19.     {
  20.         Connections[add1].push_back(add2);
  21.         Connections[add2].push_back(add1);
  22.     }
  23. }
  24. bool Check(HashMap& Connections, uint_fast32_t add1, uint_fast32_t add2)
  25. {
  26.     // Ten sam komputer ma polaczenie sam ze soba
  27.     if (add1==add2)
  28.         return 1;
  29.  
  30.     // Jesli nie znamy adresu to nie mozemy miec do niego polaczenia
  31.     if ((Connections.find(add1)==Connections.end()) || (Connections.find(add2)==Connections.end()))
  32.         return 0;
  33.  
  34.     std::queue<unsigned int> NodesQueue;
  35.     std::unordered_map<uint_fast32_t, bool> NodesVisited;
  36.     NodesQueue.push(add1);
  37.     NodesVisited[add1] = 1;
  38.  
  39.     while (!NodesQueue.empty())
  40.     {
  41.         add1=NodesQueue.front();
  42.         NodesQueue.pop();
  43.  
  44.         for (uint_fast32_t i{0}; i<Connections[add1].size(); ++i)
  45.         {
  46.             if (test) std::cout << "Connections[add1][i]==" << Connections[add1][i] << '\n';
  47.             if (Connections[add1][i]==add2)
  48.                 return 1;
  49.             if (!NodesVisited[Connections[add1][i]])
  50.             {
  51.                 NodesVisited[Connections[add1][i]]=1;
  52.                 NodesQueue.push(Connections[add1][i]);
  53.             }
  54.         }
  55.     } //while
  56.     return 0;
  57. }
  58.  
  59. uint_fast32_t GetIPAddress()
  60. {
  61.     uint_fast32_t a{0}, b{0}, c{0}, d{0};
  62.     char garbage{0};
  63.     std::cin >> a >> garbage >> b >> garbage >> c >> garbage >> d;
  64.     return ((a<<24)+(b<<16)+(c<<8)+d);
  65. }
  66.  
  67. void Print (HashMap& Connections)
  68. {
  69.     for (auto& element : Connections)
  70.     {
  71.         std::cout << element.first << '\t';
  72.         for (auto& element2 : element.second)
  73.             std::cout << element2 << ' ';
  74.         std::cout << '\n';
  75.     }
  76. }
  77.  
  78. int main()
  79. {
  80.     char request{0};
  81.     uint_fast32_t address1{0}, address2{0};
  82.     HashMap Connections;
  83.  
  84.     while (std::cin >> request)
  85.     {
  86.         address1=GetIPAddress();
  87.         address2=GetIPAddress();
  88.         if (request=='B')
  89.         {
  90.             Add(Connections,address1,address2);
  91.         }
  92.         if (request=='T')
  93.         {
  94.             if(Check(Connections,address1,address2))
  95.                 std::cout << "T\n";
  96.             else
  97.                 std::cout << "N\n";
  98.         }
  99.     }//while
  100.     if (test) Print(Connections);
  101.     return 0;
  102. }//main
  103.  
Success #stdin #stdout 0s 4544KB
comments (?)
stdin
copy 
B 100.100.100.1 100.100.100.2
B 100.100.100.1 100.100.100.3
B 100.100.100.10 100.100.100.11
T 100.100.100.1 100.100.100.3
T 100.100.100.10 100.100.100.2
T 100.100.100.10 100.100.100.11
B 100.100.100.11 100.100.100.2
T 100.100.100.10 100.100.100.3
T 100.100.100.100 100.100.100.103
stdout
copy 
T
N
T
T
N
https://ideone.com/Po9qc1
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!