CCC '21 S4 - Daily Commute

Please read the problem description:

https://www.cemc.uwaterloo.ca/contests/computing/2021/ccc/seniorEF.pdf

The problem is BFS question. If you want to get full marks, you should read the problem carefully. must understand:

1. Walk to Nth station

2. Each day only has one train running from the first station to the Nth station. you must understand "one". This is very important, this means if you can not do train->walk->train, because you need to wait for the train coming that only one train.

The solution should be:

1. Do BFS to get the distance that each station walks to the Nth station.

2. Each station m (position) to Nth station minimum distance is:

min(take train route, train + walk)

3. Make an ordered set to store all minimum distances to the Nth station.

4. Each day, swap two stations, and update the ordered set, the 0 elements of

the set is one answer.

#include <bits/stdc++.h>

#include <iostream>

#include <vector>

#include <string.h>

#include <queue>

using namespace std;

vector<int> fixedRoute[200001];

int valueToPos[200001];

int position[200001];

int dis[200001];

bool visited[200001];

int wdist[200001];

int N, W, D;

void bfs(int n){

bool vis[n+1];

memset(vis, 0, sizeof(vis));

vis[n] = true; // Start at statio N

wdist[n] = 0;

queue<int> q;

q.push(n);

while(!q.empty()){

int cur_station = q.front();

q.pop();

for( int i = 0; i < fixedRoute[cur_station].size(); i++)

{

if(!vis[fixedRoute[cur_station][i]]){

wdist[fixedRoute[cur_station][i]] = wdist[cur_station] + 1;

vis[fixedRoute[cur_station][i]] = true;

q.push(fixedRoute[cur_station][i]);

}

}

}

}

int main() {

cin >> N;

cin >> W;

cin >> D;

for(int i = 0; i < W; i++){

int m ,n;

cin >> m;

cin >> n;

fixedRoute[n].push_back(m);

}

memset(wdist, 200002, 200001*sizeof(int));

bfs(N);

int subwayline[N+1]; // subwayline[0] is unused, subwayline[1] to subwayline[n] stores the station number at that point

multiset<int> culdist; // culmitive distance... doesn't matter which station it's from / to all we care about is what the distance is and a multimap is perfect for this.

for(int a=1;a<=N;++a){

cin >> subwayline[a];

// Subway distance is = index of subwayline -1

culdist.insert(a-1 + wdist[subwayline[a]]);

// Distance on train + walking distance

}

// For each "station swap"

for(int i=0;i<D;++i){

int station1, station2;

cin >> station1 >> station2; // Gives station location

// Get old distance and remove from multiset

int station1OldDist = station1-1 + wdist[subwayline[station1]];

int station2OldDist = station2-1 + wdist[subwayline[station2]];

culdist.erase(culdist.find(station1OldDist));

culdist.erase(culdist.find(station2OldDist));

// Swap opreration

swap(subwayline[station1], subwayline[station2]);

// Add new distances

culdist.insert(station1-1 + wdist[subwayline[station1]]);

culdist.insert(station2-1 + wdist[subwayline[station2]]);

// Output the minimum distance - multisets are dynamically sorted internally

}

return 0;

}