fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <queue>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. class Solution {
  10. private:
  11.     vector<vector<int>> adj;
  12.     int n;
  13.  
  14.     // BFS to find distance between two nodes
  15.     int bfs(int start, int end) {
  16.         if (start == end) return 0;
  17.  
  18.         vector<int> dist(n + 1, -1);
  19.         queue<int> q;
  20.         q.push(start);
  21.         dist[start] = 0;
  22.  
  23.         while (!q.empty()) {
  24.             int u = q.front();
  25.             q.pop();
  26.  
  27.             if (u == end) return dist[u];
  28.  
  29.             for (int v : adj[u]) {
  30.                 if (dist[v] == -1) {
  31.                     dist[v] = dist[u] + 1;
  32.                     q.push(v);
  33.                 }
  34.             }
  35.         }
  36.  
  37.         return -1;
  38.     }
  39.  
  40. public:
  41.     long long findTotalBandwidth(int network_nodes, vector<int>& network_from, 
  42.                                   vector<int>& network_to, vector<int>& port) {
  43.         n = network_nodes;
  44.         adj.resize(n + 1);
  45.  
  46.         // Build adjacency list (1-indexed)
  47.         for (int i = 0; i < network_from.size(); i++) {
  48.             int u = network_from[i];
  49.             int v = network_to[i];
  50.             adj[u].push_back(v);
  51.             adj[v].push_back(u);
  52.         }
  53.  
  54.         // Group computers by port
  55.         unordered_map<int, vector<int>> portGroups;
  56.         for (int i = 0; i < port.size(); i++) {
  57.             portGroups[port[i]].push_back(i + 1); // 1-indexed
  58.         }
  59.  
  60.         long long totalBandwidth = 0;
  61.  
  62.         // For each port group, calculate sum of distances
  63.         for (auto& [p, computers] : portGroups) {
  64.             int groupSize = computers.size();
  65.  
  66.             // Calculate distance between all pairs in this group
  67.             for (int i = 0; i < groupSize; i++) {
  68.                 for (int j = i + 1; j < groupSize; j++) {
  69.                     int dist = bfs(computers[i], computers[j]);
  70.                     totalBandwidth += dist;
  71.                 }
  72.             }
  73.         }
  74.  
  75.         return totalBandwidth;
  76.     }
  77. };
  78.  
  79. int main() {
  80.     Solution sol;
  81.  
  82.     // Test Case 1: Sample Case 0
  83.     cout << "Test Case 1:" << endl;
  84.     {
  85.         int network_nodes = 5;
  86.         vector<int> network_from = {1, 1, 2, 4};
  87.         vector<int> network_to = {2, 3, 4, 5};
  88.         vector<int> port = {1, 2, 2, 3, 2};
  89.  
  90.         long long result = sol.findTotalBandwidth(network_nodes, network_from, network_to, port);
  91.         cout << "Expected: 8" << endl;
  92.         cout << "Got: " << result << endl;
  93.         cout << (result == 8 ? "PASS" : "FAIL") << endl << endl;
  94.     }
  95.  
  96.     // Test Case 2: Sample Case 1
  97.     cout << "Test Case 2:" << endl;
  98.     {
  99.         int network_nodes = 3;
  100.         vector<int> network_from = {1, 2};
  101.         vector<int> network_to = {2, 3};
  102.         vector<int> port = {1, 2, 3};
  103.  
  104.         long long result = sol.findTotalBandwidth(network_nodes, network_from, network_to, port);
  105.         cout << "Expected: 0" << endl;
  106.         cout << "Got: " << result << endl;
  107.         cout << (result == 0 ? "PASS" : "FAIL") << endl << endl;
  108.     }
  109.  
  110.     // Test Case 3: Example from problem description
  111.     cout << "Test Case 3:" << endl;
  112.     {
  113.         int network_nodes = 5;
  114.         vector<int> network_from = {1, 1, 2, 2};
  115.         vector<int> network_to = {2, 3, 4, 5};
  116.         vector<int> port = {3, 1, 3, 3, 1};
  117.  
  118.         long long result = sol.findTotalBandwidth(network_nodes, network_from, network_to, port);
  119.         cout << "Expected: 5" << endl;
  120.         cout << "Got: " << result << endl;
  121.         cout << (result == 5 ? "PASS" : "FAIL") << endl << endl;
  122.     }
  123.  
  124.     // Test Case 4: All same port
  125.     cout << "Test Case 4: All same port" << endl;
  126.     {
  127.         int network_nodes = 4;
  128.         vector<int> network_from = {1, 2, 3};
  129.         vector<int> network_to = {2, 3, 4};
  130.         vector<int> port = {1, 1, 1, 1};
  131.  
  132.         long long result = sol.findTotalBandwidth(network_nodes, network_from, network_to, port);
  133.         // Distances: (1,2)=1, (1,3)=2, (1,4)=3, (2,3)=1, (2,4)=2, (3,4)=1
  134.         // Total = 1+2+3+1+2+1 = 10
  135.         cout << "Expected: 10" << endl;
  136.         cout << "Got: " << result << endl;
  137.         cout << (result == 10 ? "PASS" : "FAIL") << endl << endl;
  138.     }
  139.  
  140.     // Test Case 5: Star topology
  141.     cout << "Test Case 5: Star topology" << endl;
  142.     {
  143.         int network_nodes = 5;
  144.         vector<int> network_from = {1, 1, 1, 1};
  145.         vector<int> network_to = {2, 3, 4, 5};
  146.         vector<int> port = {1, 1, 1, 1, 1};
  147.  
  148.         long long result = sol.findTotalBandwidth(network_nodes, network_from, network_to, port);
  149.         // Center is node 1, distances from center: all 1
  150.         // Pairs: (1,2)=1, (1,3)=1, (1,4)=1, (1,5)=1
  151.         // Non-center pairs: (2,3)=2, (2,4)=2, (2,5)=2, (3,4)=2, (3,5)=2, (4,5)=2
  152.         // Total = 4*1 + 6*2 = 16
  153.         cout << "Expected: 16" << endl;
  154.         cout << "Got: " << result << endl;
  155.         cout << (result == 16 ? "PASS" : "FAIL") << endl << endl;
  156.     }
  157.  
  158.     // Test Case 6: Two separate groups
  159.     cout << "Test Case 6: Two groups" << endl;
  160.     {
  161.         int network_nodes = 4;
  162.         vector<int> network_from = {1, 2, 3};
  163.         vector<int> network_to = {2, 3, 4};
  164.         vector<int> port = {1, 1, 2, 2};
  165.  
  166.         long long result = sol.findTotalBandwidth(network_nodes, network_from, network_to, port);
  167.         // Group 1: nodes 1,2 -> dist(1,2) = 1
  168.         // Group 2: nodes 3,4 -> dist(3,4) = 1
  169.         // Total = 1+1 = 2
  170.         cout << "Expected: 2" << endl;
  171.         cout << "Got: " << result << endl;
  172.         cout << (result == 2 ? "PASS" : "FAIL") << endl << endl;
  173.     }
  174.  
  175.     return 0;
  176. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Test Case 1:
Expected: 8
Got: 8
PASS

Test Case 2:
Expected: 0
Got: 0
PASS

Test Case 3:
Expected: 5
Got: 6
FAIL

Test Case 4: All same port
Expected: 10
Got: 7
FAIL

Test Case 5: Star topology
Expected: 16
Got: 12
FAIL

Test Case 6: Two groups
Expected: 2
Got: 2
PASS
https://ideone.com/kFp5Zd
language:
C++ (gcc 8.3)
created:
12 days ago
visibility:
public

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!