Anime Shops

#include <bits/stdc++.h>
#include <iterator>
using namespace std;

#define MAXN 100001
#define INF 1e7

typedef pair<int, int> pii;
priority_queue<pii> q;
map<int, vector<vector<int>>> adj;
vector<int> dist;
vector<int> parent;
int srank[MAXN];
int n, m, k;

int find_set(int u) {
  if (parent[u] == -1)
    return u;

  return parent[u] = find_set(parent[u]);
}

void unite(int a, int b) {
  a = find_set(a);
  b = find_set(b);

  if (a != b) {
    if (srank[b] > srank[a])
      swap(a, b);
    parent[b] = a;
    srank[a] += srank[b];

    if (adj.count(b)) {
      for (int i = 1; i < n + 1; ++i) {
        adj[a][i].insert(adj[a][i].end(), make_move_iterator(adj[b][i].begin()),
                         make_move_iterator(adj[b][i].end()));
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  cin >> n >> m >> k;

  vector<bool> shop(n + 1, false);

  int c;
  for (int i = 0; i < k; ++i) {
    cin >> c;
    shop[c] = true;
  }

  // vector<pii> edges(m);
  parent.assign(n + 1, -1);
  fill_n(srank, n + 1, 1);

  int a, b;
  for (int i = 0; i < m; ++i) {
    cin >> a >> b;

    unite(a, b);
    auto s = find_set(a);
    if (!adj.count(s)) {
      vector<vector<int>> v(n + 1);
      adj[s] = v;
      // adj[s].assign(n + 1, {});
    }
    adj[s][a].emplace_back(b);
    adj[s][b].emplace_back(a);
    // edges[i] = {a, b};
  }

  // Group 2
  if (m == n - 1) {
    dist.assign(n + 1, INF);
    int seen = INF;
    for (int i = 1; i < n + 1; ++i) {
      dist[i] = seen + 1;
      if (shop[i]) {
        seen = 0;
      } else {
        seen++;
      }
    }
    seen = INF;
    for (int i = n; i > 0; --i) {
      dist[i] = min(seen + 1, dist[i]);
      if (shop[i]) {
        seen = 0;
      } else {
        seen++;
      }
    }

    for (int i = 1; i < n + 1; ++i) {
      cout << ((dist[i] < INF) ? dist[i] : -1) << ' ';
    }
    return 0;
  }

  for (int x = 1; x < n + 1; ++x) {
    dist.assign(n + 1, INF);
    dist[x] = 0;

    q = {};
    q.push({0, x});

    auto g = find_set(x);
    int target = -1;

    if (adj.count(g))
      while (!q.empty()) {
        int a = q.top().second;

        // Found the shortest path to an anime shop
        if (shop[a] && a != x) {
          target = a;

          // printf("shortest %d -> %d dist: %d\n", x, a, dist[a]);
          break;
        }

        q.pop();
        for (auto b : adj[g][a]) {
          if (dist[a] + 1 < dist[b]) {
            dist[b] = dist[a] + 1;
            q.push({-dist[b], b});
          }
        }
      }

    cout << (target == -1 ? target : dist[target]) << ' ';
  }
  cout << '\n';
}

Test 1

Group: 1, 3

Verdict: ACCEPTED

Test 2

Group: 1, 3

Verdict: ACCEPTED

Test 3

Group: 1, 3

Verdict: ACCEPTED

Test 4

Group: 1, 3

Verdict: ACCEPTED

Test 5

Group: 3

Verdict: RUNTIME ERROR

Test 6

Group: 3

Verdict: RUNTIME ERROR

Test 7

Group: 3

Verdict: RUNTIME ERROR

Test 8

Group: 3

Verdict: RUNTIME ERROR

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 2, 3

Verdict: ACCEPTED

Test 11

Group: 2, 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: WRONG ANSWER

Test 13

Group: 3

Verdict: WRONG ANSWER

Test 14

Group: 3

Verdict: WRONG ANSWER

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED