oj.uz

Submission #965400

# Submission time Handle Problem Language Result Execution time Memory
965400 2024-04-18T12:50:26 Z abczz Passport (JOI23_passport) C++14
6 / 100
 741 ms 146716 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25688 KB Output is correct
2 Correct 9 ms 25692 KB Output is correct
3 Correct 6 ms 25692 KB Output is correct
4 Correct 741 ms 146716 KB Output is correct
5 Correct 350 ms 97248 KB Output is correct
6 Correct 245 ms 87040 KB Output is correct
7 Correct 168 ms 84672 KB Output is correct
8 Correct 162 ms 96376 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26064 KB Output is correct
2 Correct 6 ms 25692 KB Output is correct
3 Correct 6 ms 25692 KB Output is correct
4 Correct 6 ms 25692 KB Output is correct
5 Correct 6 ms 25692 KB Output is correct
6 Correct 6 ms 25692 KB Output is correct
7 Correct 6 ms 25948 KB Output is correct
8 Incorrect 6 ms 25692 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26064 KB Output is correct
2 Correct 6 ms 25692 KB Output is correct
3 Correct 6 ms 25692 KB Output is correct
4 Correct 6 ms 25692 KB Output is correct
5 Correct 6 ms 25692 KB Output is correct
6 Correct 6 ms 25692 KB Output is correct
7 Correct 6 ms 25948 KB Output is correct
8 Incorrect 6 ms 25692 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26064 KB Output is correct
2 Correct 6 ms 25692 KB Output is correct
3 Correct 6 ms 25692 KB Output is correct
4 Correct 6 ms 25692 KB Output is correct
5 Correct 6 ms 25692 KB Output is correct
6 Correct 6 ms 25692 KB Output is correct
7 Correct 6 ms 25948 KB Output is correct
8 Incorrect 6 ms 25692 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25688 KB Output is correct
2 Correct 9 ms 25692 KB Output is correct
3 Correct 6 ms 25692 KB Output is correct
4 Correct 741 ms 146716 KB Output is correct
5 Correct 350 ms 97248 KB Output is correct
6 Correct 245 ms 87040 KB Output is correct
7 Correct 168 ms 84672 KB Output is correct
8 Correct 162 ms 96376 KB Output is correct
9 Correct 6 ms 26064 KB Output is correct
10 Correct 6 ms 25692 KB Output is correct
11 Correct 6 ms 25692 KB Output is correct
12 Correct 6 ms 25692 KB Output is correct
13 Correct 6 ms 25692 KB Output is correct
14 Correct 6 ms 25692 KB Output is correct
15 Correct 6 ms 25948 KB Output is correct
16 Incorrect 6 ms 25692 KB Output isn't correct
17 Halted 0 ms 0 KB -