Passengers on the Last Bus
National Olympiad — National round (2025 season)
Submission name: bus.cpp
Problem summary
The driver serves endpoint stops, but an interior stop only when its fixed ticket monitor lists both boarders and destinations there. Count nonboarders and boarded riders who miss their requested destination.
Input
n m followed by m pairs a b, sorted by boarding stop.
Output
Unable-to-board count, then boarded-but-missed-destination count.
Constraints
2≤n,m≤100000; 1≤a<b≤n; at most 1000 wait at each stop.
Worked example
Input and output for the worked example discussed below.
Input
5 5 1 2 1 4 2 5 3 4 3 5
Output
2 1
Solution analysis
- Mark every boarding and destination stop from all tickets. These marks never change, even when a passenger cannot board, because the driver reads only the fixed monitor.
- A stop is served if it is an endpoint or both marks are present. For each ticket, first test whether boarding is possible; only boarded riders can contribute to the missed-destination count.
- The sample serves stops 1,2,5. Both people waiting at stop 3 cannot board. The passenger from 1 to 4 boards but misses stop 4, giving outputs 2 and 1.
Why it works
Presence flags exactly describe the monitor, so their conjunction and endpoint exceptions identify the served stops. The ordered ticket classification then counts precisely the two requested populations.
Watch out. Do not remove destinations for passengers who fail to board. Never count those nonboarders in the second output.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int stops;
int count;
cin>>stops>>count;
vector<pair<int,int>>tickets(count);
vector<bool>boarding(stops+1,false);
vector<bool>leaving(stops+1,false);
for(auto&[from,to]:tickets){
cin>>from>>to;
boarding[from]=true;
leaving[to]=true;
}
auto served=[&](int stop){
return stop==1||stop==stops||(boarding[stop]&&leaving[stop]);
};
int cannotBoard=0;
int cannotLeave=0;
for(auto[from,to]:tickets){
// Count nonboarders before testing destinations of actual riders.
if(!served(from)){
cannotBoard++;
}
else if(!served(to)){
cannotLeave++;
}
}
cout<<cannotBoard<<'\n'<<cannotLeave<<'\n';
}