Submission #965418

#	Time	Username	Problem	Language	Result	Execution time	Memory
965418		abczz	Passport (JOI23_passport)	C++14	100 / 100	1433 ms	162880 KiB

passport

#include <iostream>
#include <vector>
#include <array>
#include <queue>
#define ll long long

using namespace std;

vector <array<ll, 2>> adj[1000000];
priority_queue <array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
ll n, q, a, b, A[200000], dist[1000000][4];

void build(ll id, ll l, ll r) {
  if (l == r) {
    adj[l].push_back({n+id, 1});
    return;
  }
  ll mid = (l+r)/2;
  build(id*2, l, mid);
  build(id*2+1, mid+1, r);
  adj[n+id*2].push_back({n+id, 0});
  adj[n+id*2+1].push_back({n+id, 0});
}

void query(ll id, ll l, ll r, ll ql, ll qr, ll u) {
  if (qr < l || r < ql) return;
  else if (ql <= l && r <= qr) {
    adj[n+id].push_back({u, 0});
    return;
  }
  ll mid = (l+r)/2;
  query(id*2, l, mid, ql, qr, u);
  query(id*2+1, mid+1, r, ql, qr, u);
}


int main() {
  cin >> n;
  build(1, 0, n-1);
  for (int i=0; i<5*n; ++i) {
    for (int j=0; j<4; ++j) {
      dist[i][j] = 1e18;
    }
  }
  for (int i=0; i<n; ++i) {
    cin >> a >> b;
    --a, --b;
    query(1, 0, n-1, a, b, i);
    if (!a) A[i] |= 1;
    if (b == n-1) A[i] |= 2;
    if (A[i]) {
      dist[i][A[i]] = 0;
      pq.push({0, i, A[i]});
    }
  }
  while (!pq.empty()) {
    auto [w, u, x] = pq.top();
    pq.pop();
    if (dist[u][x] != w) continue;
    if (dist[u][3] > dist[u][1] + dist[u][2]) {
      dist[u][3] = dist[u][1] + dist[u][2];
      pq.push({dist[u][3], u, 3});
    }
    for (auto [v, z] : adj[u]) {
      if (dist[v][x] > w+z) {
        dist[v][x] = w+z;
        pq.push({w+z, v, x});
      }
    }
  }
  cin >> q;
  while (q--) {
    cin >> a;
    --a;
    if (dist[a][3] == 1e18) cout << "-1\n";
    else cout << dist[a][3]+1 << '\n';
  }
}

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:57:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     auto [w, u, x] = pq.top();
      |          ^
passport.cpp:64:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |     for (auto [v, z] : adj[u]) {
      |               ^

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