Submission #1267743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267743		julia_08	Railway Trip 2 (JOI22_ho_t4)	C++20	0 / 100	1416 ms	589824 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; 

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){

      int cnt = 1;

      int sz = min(b - a + 1, k);

      while(cnt <= sz){
        adj[a].push_back(b);
        a ++;
        cnt ++;
      }

    } else{

      int cnt = 1;

      int sz = min(a - b + 1, k);

      while(cnt <= sz){
        adj[a].push_back(b);
        a --;
        cnt ++;
      }

    }
    
  }

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

    if(adj[i].size() <= 2) continue;

    swap(adj[i].back(), adj[i][1]);

    while(adj[i].size() > 2) adj[i].pop_back();

  }

  /*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: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13