Approach
Breadth-first search
For Implement Router, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 59 lines of C++ from the credited upstream file 3508.cpp.
- The implementation visibly relies on sequence storage, ordered lookup, work queue, cached states.
- No explicit loop blocks detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1struct Packet {2 int source;3 int destination;4 int timestamp;5 6 bool operator<(const Packet& other) const {7 return source < other.source ||8 (source == other.source && destination < other.destination) ||9 (source == other.source && destination == other.destination &&10 timestamp < other.timestamp);11 }12};13 14class Router {15 public:16 Router(int memoryLimit) : memoryLimit(memoryLimit) {}17 18 bool addPacket(int source, int destination, int timestamp) {19 const Packet packet{source, destination, timestamp};20 if (uniquePackets.find(packet) != uniquePackets.end())21 return false;22 if (packetQueue.size() == memoryLimit)23 forwardPacket();24 packetQueue.push(packet);25 uniquePackets.insert(packet);26 destinationTimestamps[destination].push_back(timestamp);27 return true;28 }29 30 vector<int> forwardPacket() {31 if (packetQueue.empty())32 return {};33 const Packet nextPacket = packetQueue.front();34 packetQueue.pop();35 uniquePackets.erase(nextPacket);36 ++processedPacketIndex[nextPacket.destination];37 return {nextPacket.source, nextPacket.destination, nextPacket.timestamp};38 }39 40 int getCount(int destination, int startTime, int endTime) {41 if (destinationTimestamps.find(destination) == destinationTimestamps.end())42 return 0;43 const vector<int>& timestamps = destinationTimestamps[destination];44 const int startIndex = processedPacketIndex[destination];45 const auto lowerBound = lower_bound(timestamps.begin() + startIndex,46 timestamps.end(), startTime);47 const auto upperBound =48 upper_bound(timestamps.begin() + startIndex, timestamps.end(), endTime);49 return upperBound - lowerBound;50 }51 52 private:53 const int memoryLimit;54 set<Packet> uniquePackets;55 queue<Packet> packetQueue;56 map<int, vector<int>> destinationTimestamps;57 map<int, int> processedPacketIndex;58};59