Anime Shops

input/code.cpp: In function 'bool next_town_has_shop(City, std::vector<City>)':
input/code.cpp:18:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for (int j = 0; j < current_city.neighboring_cities.size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp: In function 'int search_shop(City, std::vector<City>, int)':
input/code.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i = 0; i < current_city.neighboring_cities.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:91:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<City>::size_type' {aka 'long unsigned int'} [-...

#include <iostream>
#include <vector>

using namespace std;

class City {
public:
  int id;
  bool has_shop;
  vector<int> neighboring_cities;
  bool next_town_has_shop;
};

bool next_town_has_shop(City current_city, vector<City> all_cities) {
  bool neigboring_city_has_shop = false;
  for (int j = 0; j < current_city.neighboring_cities.size(); j++) {
    int neighbour_id = current_city.neighboring_cities[j];

    if (all_cities[neighbour_id].has_shop) {
      neigboring_city_has_shop = true;
      break;
    }
  }

  return neigboring_city_has_shop;
}

int search_shop(City current_city, vector<City> all_cities, int distance = 0) {
  distance++;
  bool has_shop = next_town_has_shop(current_city, all_cities);

  if (has_shop) {
    return distance;
  } else {
    distance = -1;
    for (int i = 0; i < current_city.neighboring_cities.size(); i++) {
      City next_city = all_cities[current_city.neighboring_cities[i]];

      if (next_town_has_shop(next_city, all_cities)) {
        distance = 2;
        break;
      }
    }
  }
  return distance;
}

int main() {
  int n, m, k;
  cin >> n >> m >> k;

  vector<City> cities;

  // populate cities
  for (int i = 0; i < n; i++) {
    int id = i + 1;
    City city;
    city.id = id;
    city.has_shop = false; // default to false
    city.next_town_has_shop = false;
    cities.push_back(city);
  }

  // mark the cities which have a shop
  for (int i = 0; i < k; i++) {
    int id;
    cin >> id;

    cities[id].has_shop = true;
  }

  // connect cities with roads
  for (int i = 0; i < m; i++) {
    int city_a, city_b;
    cin >> city_a >> city_b;

    // remember id of city is index +1 of cities
    City from_city = cities[city_a - 1];
    from_city.neighboring_cities.push_back(city_b);
    cities[city_a - 1] = from_city;

    // make road bidirectional
    City to_city = cities[city_b - 1];
    to_city.neighboring_cities.push_back(city_a);
    cities[city_b - 1] = to_city;
  }

  // first search
  for (int i = 0; i < cities.size(); i++) {
    City city = cities[i];

    if (next_town_has_shop(city, cities)) {
      city.next_town_has_shop = true;
      cities[i] = city;
    }
  }

  for (int i = 0; i < cities.size(); i++) {
    City city = cities[i];

    // if the neighboiring cities have no shops, but the
    int distance = 1;
    if (!city.next_town_has_shop) {
      distance = -1;
      for (int j = 0; j < city.neighboring_cities.size(); j++) {
        int neighbour_id = city.neighboring_cities[j];
        City neighbour = cities[neighbour_id];

        if (neighbour.next_town_has_shop) {
          distance = 2;
        }
      }
    }

    cout << distance << " ";

    // cout << city.next_town_has_shop << " ";
    // cout << city.has_shop << " ";
    // cout << "id: " << city.id << endl;
    // cout << "has_shop: " << city.has_shop << endl;
    // cout << "next_town_has_shop: " << city.next_town_has_shop << endl;
    // cout << "amount of neighbours: " << city.neighboring_cities.size() <<
    // endl; cout << "distance: " << distance << endl; cout << endl;
  }
  cout << endl;

  return 0;
}

Test 1

Group: 1, 3

Verdict: WRONG ANSWER

Test 2

Group: 1, 3

Verdict: WRONG ANSWER

Test 3

Group: 1, 3

Verdict: WRONG ANSWER

Test 4

Group: 1, 3

Verdict: ACCEPTED

Test 5

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED