Skip to content

Instantly share code, notes, and snippets.

@wpsadi

wpsadi/sol.cpp

Created October 3, 2024 07:12
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save wpsadi/035802bc8dcdbd94255ecf06b0550b99 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save wpsadi/035802bc8dcdbd94255ecf06b0550b99 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. wpsadi created this gist Oct 3, 2024.
    57 changes: 57 additions & 0 deletions sol.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,57 @@
    #include <iostream>
    #include <vector>
    #include <unordered_set>

    using namespace std;

    string can_travel(int N, int M, vector<int>& route_A, vector<int>& route_B, int X, int Y) {
    // Convert both routes to sets for quick lookup
    unordered_set<int> set_A(route_A.begin(), route_A.end());
    unordered_set<int> set_B(route_B.begin(), route_B.end());

    // Case 1: Direct route in route A or B
    if (set_A.count(X) && set_A.count(Y)) {
    return "Yes";
    }
    if (set_B.count(X) && set_B.count(Y)) {
    return "Yes";
    }

    // Case 2: Check if there's a common stop and we can switch routes
    for (int stop : set_A) {
    if (set_B.count(stop)) {
    if ((set_A.count(X) && set_B.count(Y)) || (set_B.count(X) && set_A.count(Y))) {
    return "Yes";
    }
    }
    }

    // No valid route found
    return "No";
    }

    int main() {
    int N, M, X, Y;
    // Input number of stops in routes A and B
    cin >> N >> M;

    vector<int> route_A(N), route_B(M);

    // Input stops for route A
    for (int i = 0; i < N; i++) {
    cin >> route_A[i];
    }

    // Input stops for route B
    for (int i = 0; i < M; i++) {
    cin >> route_B[i];
    }

    // Input the source and destination stops
    cin >> X >> Y;

    // Get the result of travel possibility and print it
    cout << can_travel(N, M, route_A, route_B, X, Y) << endl;

    return 0;
    }