Submission #1267747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267747		julia_08	Railway Trip 2 (JOI22_ho_t4)	C++20	27 / 100	2093 ms	29484 KiB

Main

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

const int MAXN = 1e5 + 10;
const int MAXQ = 5e4 + 10;

vector<int> adj[MAXN];

int dist[MAXN], marc[MAXN];

int n, k; 

vector<pair<int, int>> pre[MAXN], nxt[MAXN];

void bfs(int x){

  set<int> s;

  for(int i=1; i<=n; i++){
    dist[i] = 1e9;
    marc[i] = 0;
    s.insert(i);
  }

  queue<int> q;

  marc[x] = 1;
  dist[x] = 0;

  q.push(x);
  s.erase(x);

  while(!q.empty()){

    int v = q.front();
    q.pop();

    for(auto u : adj[v]){

      vector<int> to_erase;

      if(v < u){

        auto w = s.upper_bound(v);

        while(w != s.end() && *w <= u){

          dist[*w] = dist[v] + 1;
          marc[*w] = 1;

          q.push(*w);
          
          to_erase.push_back(*w);
          ++ w;

        } 

      } else{

        auto w = s.lower_bound(u);

        while(w != s.end() && *w < v){

          dist[*w] = dist[v] + 1;
          marc[*w] = 1;

          q.push(*w);

          to_erase.push_back(*w);
          ++ w;

        }

      }

      for(auto x : to_erase) s.erase(x);


    }

  }

}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> k;

  int cur = n;

  int m; cin >> m;

  while(m--){

    int a, b; cin >> a >> b;

    if(a < b){

      nxt[a].push_back({b, 1});
      nxt[min(b + 1, a + k)].push_back({b, -1});

    } else{

      pre[a].push_back({b, 1});
      pre[max(b - 1, a - k)].push_back({b, -1});

    }
    
  }

  multiset<int> ms;

  for(int i=1; i<=n; i++){

    for(auto j : nxt[i]){
      if(j.second == -1){
        ms.erase(ms.find(j.first));
      } else ms.insert(j.first);
    }

    if(!ms.empty()) adj[i].push_back(*ms.rbegin());

  }

  ms.clear();

  for(int i=n; i>=1; i--){

    for(auto j : pre[i]){
      if(j.second == -1){
        ms.erase(ms.find(j.first));
      } else ms.insert(j.first);
    }

    if(!ms.empty()) adj[i].push_back(*ms.begin());

  }

  /*for(int i=1; i<=n; i++){
    cout << i << ": ";
    for(auto j : adj[i]) cout << j << " ";
    cout << "\n";
  }*/

  int q; cin >> q;

  while(q--){
    int a, b; cin >> a >> b;
    bfs(a);
    cout << (marc[b] ? dist[b] : -1) << "\n";
  }

  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13