제출 #1164159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164159		fryingduc	Passport (JOI23_passport)	C++20	100 / 100	736 ms	86312 KiB

passport

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 8e5 + 5;

vector<pair<int, int>> g[maxn];
int n, q;
int a[maxn], b[maxn];
int rv[maxn], sl[maxn], sr[maxn];
int cd[2][maxn];
long long d[maxn];
int mx_nodes;

void add_edge(int u, int v, int w) {
  g[u].emplace_back(v, w);
}

void build(int ind = 1, int l = 1, int r = n) {
  sl[ind] = l, sr[ind] = r;
  mx_nodes = max(mx_nodes, ind);
  if (l == r) {
    rv[l] = ind;
    return;
  }
  int mid = (l + r) >> 1;
  build(ind << 1, l, mid);
  build(ind << 1 | 1, mid + 1, r);
  add_edge(ind << 1, ind, 0);
  add_edge(ind << 1 | 1, ind, 0);
}

void update(int pos, int x, int y, int ind = 1, int l = 1, int r = n) {
  if (l > y || r < x) return;
  if (x <= l and r <= y) {
    add_edge(ind, rv[pos], 1);
    return;
  }
  int mid = (l + r) >> 1;
  update(pos, x, y, ind << 1, l, mid);
  update(pos, x, y, ind << 1 | 1, mid + 1, r);
}

void bfs(int d[], int src) {
  for (int i = 1; i <= mx_nodes; ++i) {
    d[i] = 1e9;
  }
  deque<pair<int, int>> dq;
  dq.emplace_back(0, src);
  d[src] = 0;
  while (!dq.empty()) {
    auto [dist, u] = dq.front();
    dq.pop_front();
    if (d[u] < dist) continue;
    for (auto [v, w] : g[u]) {
      if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        if (w == 1) dq.emplace_back(d[v], v);
        else dq.push_front(make_pair(d[v], v));
      }
    }
  }
}

void solve() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i] >> b[i];
  }
  build();
  for (int i = 1; i <= n; ++i) {
    update(i, a[i], b[i]);
  }
  bfs(cd[0], rv[1]);
  bfs(cd[1], rv[n]);
  using T = pair<long long, int>;
  priority_queue<T, vector<T>, greater<T>> pq;
  for (int i = 1; i <= mx_nodes; ++i) {
    d[i] = cd[0][i] + cd[1][i];
    if (d[i] < 1e9) {
      if (sl[i] == sr[i]) {
        if (sl[i] > 1 and sr[i] < n) --d[i];
        pq.emplace(d[i], i);
      }
    }
  }
  while (!pq.empty()) {
    auto [dist, u] = pq.top();
    pq.pop();
    if (d[u] < dist) continue;
    for (auto [v, w] : g[u]) {
      if (d[v] > d[u] + w) {
        pq.emplace(d[v] = d[u] + w, v);
      }
    }
  }
  cin >> q;
  while (q--) {
    int u; cin >> u;
    cout << (d[rv[u]] >= 1e9 ? -1 : d[rv[u]]) << '\n';
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46