Submission #965400

#	Time	Username	Problem	Language	Result	Execution time	Memory
965400		abczz	Passport (JOI23_passport)	C++14	6 / 100	741 ms	146716 KiB

passport

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

using namespace std;

vector <array<ll, 2>> adj[1000000];
queue <array<ll, 3>> Q[2];
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;
      Q[0].push({i, A[i], 0});
    }
  }
  while (!Q[0].empty()) {
    while (!Q[0].empty()) {
      auto [u, x, w] = Q[0].front();
      //cout << u << " " << x << " " << w << endl;
      Q[0].pop();
      if (dist[u][3] > dist[u][1] + dist[u][2]) {
        dist[u][3] = dist[u][1] + dist[u][2];
        Q[0].push({u, 3, dist[u][3]});
      }
      for (auto [v, z] : adj[u]) {
        if (dist[v][x] == 1e18) {
          dist[v][x] = w+z;
          Q[z].push({v, x, w+z});
        }
      }
    }
    swap(Q[0], Q[1]);
  }
  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:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |       auto [u, x, w] = Q[0].front();
      |            ^
passport.cpp:64:17: 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: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46