Anime Shops

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

    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;
  }

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

    int n_neighbours_with_shops = search_shop(city, cities);
    cout << n_neighbours_with_shops << " ";
  }
  cout << endl;

  return 0;
}

Test 1

Group: 1, 3

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 2

Group: 1, 3

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 3

Group: 1, 3

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

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