/* * Code for hogwarts. * * Author: Giada Franz * * Description: O(m + max_time)-time solution using BFS + sweeping line on time * */ #include <vector> #include <iostream> using namespace std; const int INF = 1000000000; const int MAX_TIME = 5000000; const int MAXN = 1000000; vector < pair <int, int> > edges_[MAXN+1]; vector <int> reached_[MAX_TIME+1]; bool done_[MAXN+1]; int distance_[MAXN+1]; int raggiungi(int N, int M, int A[], int B[], int appear[], int disappear[]) { for (int i = 0; i < M; i++) { edges_[A[i]].push_back(make_pair(i, B[i])); edges_[B[i]].push_back(make_pair(i, A[i])); } for (int i = 0; i < N; i++) { done_[i] = false; distance_[i] = INF; } reached_[0].push_back(0); distance_[0] = 0; for (int t = 0; t <= MAX_TIME; t++) { for (int v : reached_[t]) { if (!done_[v]) { for (auto edge : edges_[v]) { int staircase = edge.first; int neighbor = edge.second; int time = max(distance_[v], appear[staircase])+1; if (!done_[neighbor] and distance_[v] < disappear[staircase] and time < distance_[neighbor]) { distance_[neighbor] = time; reached_[time].push_back(neighbor); } } done_[v] = true; } } } return (distance_[N-1] == INF)? -1 : distance_[N-1]; }