UNIVERSE - Time limit exceeded issue [C++]

general
, , ,
1

Hello, I’m trying to solve this problem Year 3017. I think my code is conceptually correct, but it is slow.

Do you have any tips to make this code faster?

#include <iostream>
#include <stdio.h>
#include <memory>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <utility>
#include <map>
#include <set>

const int MAX_PLANETS = 3e5;
const int MAX_TELEPORTS = 3e5;

using namespace std;

int getint(){
  int rv = 0, sign = 1;
  char ch = getchar_unlocked();
  while((ch > '9' || ch < '0') && ch != '-')
    ch = getchar_unlocked();
  if (ch == '-'){ // negative number
    sign = -1;
    ch = getchar_unlocked();
  }

  while(ch >= '0' && ch <= '9'){
    rv = rv * 10 + (ch - '0');
    ch = getchar_unlocked();
  }
  return sign * rv;
}

typedef pair<int, int> planet;

vector<int> tunnels[MAX_PLANETS];

// Teleports
map<planet, vector<planet>> edges;

inline void addTeleport(planet p1, planet p2);
int distance(const planet& start, const planet& goal);

int main(){
  // ios_base::sync_with_stdio(false);

  int n, m, q, dist;
  int a, b, c, d;

  // scanf("%d %d %d", &n, &m, &q);
  n = getint();
  m = getint();
  q = getint();
  // Input Tunnels
  for (int i = 0; i < n - 1; ++i){
    a = getint();
    b = getint();
    tunnels[a].push_back(b);
    tunnels[b].push_back(a);
  }

  // Input Teleports
  for (int i = 0; i < m; ++i){
    a = getint();
    b = getint();
    c = getint();
    d = getint();
    addTeleport({a, b}, {c, d});
    addTeleport({c, d}, {a, b});
  }

  for (int i = 0; i < q; ++i){
    a = getint();
    b = getint();
    c = getint();
    d = getint();
    dist = distance({a, b}, {c, d});
    if (dist == -1)
      printf("impossible\n");
    else
      printf("%d\n", dist);
  }
}

inline void addTeleport(planet p1, planet p2){
  edges[p1].push_back(p2);
}

int distance(const planet& start, const planet& goal) {
  set<planet> explored;
  map<planet, int> dists;
  queue<planet> q;

  q.push(start);
  dists[start] = 0;
  
  while(!q.empty()){
    planet cur = q.front();
    q.pop();

    int curDist = dists[cur];

    // tunnels neigh.
    for (int id : tunnels[cur.first]){
      planet p = {id, cur.second};
      if (explored.find(p) == explored.end()){
        if (p == goal)
          return curDist + 1;

        explored.insert(p);
        dists[p] = curDist + 1;
        q.push(p);
      }
    }

    // teleport neigh.
    auto it = edges.find(cur);
    if (it != edges.end()){
      for (const planet& p : it->second){
        if (explored.find(p) == explored.end()){
          if (p == goal)
            return curDist + 1;

          explored.insert(p);
          dists[p] = curDist + 1;
          q.push(p);
        }
      }
    }
  }

  return -1;
}

Thank you very much.