Submission #1023752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023752		zNatsumi	Passport (JOI23_passport)	C++17	100 / 100	594 ms	83392 KiB

passport

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5,
          INF = 1e9;

using ii = pair<int, int>;
#define fi first
#define se second

int n, q, id[N], f[2][N << 2], dp[N << 2];
vector<ii> ad[N << 2];

void build(int tl, int tr, int i){
  if(i>>1) ad[i].push_back({i>>1, 0});
  f[0][i] = f[1][i] = INF;

  if(tl == tr){
    id[tl] = i;
    return;
  }
  int tm = tl + tr >> 1;
  build(tl, tm, i<<1), build(tm+1, tr, i<<1|1);
}

void upd(int l, int r, int u, int tl, int tr, int i){
  if(r < tl || tr < l || l > r) return;
  if(l <= tl && tr <= r){
    ad[i].push_back({u, 1});
    return;
  }
  int tm = tl + tr >> 1;
  upd(l, r, u, tl, tm, i<<1), upd(l, r, u, tm+1, tr, i<<1|1);
}

void bfs(int u){
  int t = (u == n);
  u = id[u];
  deque<int> dq;
  dq.push_back(u);
  f[t][u] = 0;

  while(dq.size()){
    auto u = dq.front(); dq.pop_front();

    for(auto [v, w] : ad[u]) if(f[t][v] == INF){
      if(w == 1){
        f[t][v] = f[t][u] + 1;
        dq.push_back(v);
      }else{
        f[t][v] = f[t][u];
        dq.push_front(v);
      }
    }
  }
}

void dij(){
  priority_queue<ii, vector<ii>, greater<>> pq;
  for(int i = 1; i <= 4 * n; i++) if(dp[i] != INF) pq.push({dp[i], i});

  while(pq.size()){
    int u, d; tie(d, u) = pq.top(); pq.pop();

    if(d != dp[u]) continue;

    for(auto [v, w] : ad[u])
      if(d + w < dp[v])
        pq.push({dp[v] = d + w, v});
  }
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
  if(fopen("test.inp", "r")){
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
  }

  cin >> n;

  build(1, n, 1);

  for(int i = 1; i <= n; i++){
    int l, r; cin >> l >> r;
    upd(l, r, id[i], 1, n, 1);
  }

  bfs(1), bfs(n);
  for(int i = 2; i <= n - 1; i++) if(f[0][id[i]] != INF) f[0][id[i]]--;

  for(int i = 1; i <= 4 * n; i++){
    if(f[0][i] == INF || f[1][i] == INF) dp[i] = INF;
    else dp[i] = f[0][i] + f[1][i];
  }
  dij();

  cin >> q;
  while(q--){
    int i; cin >> i;
    cout << (dp[id[i]] == INF ? -1 : dp[id[i]]) << "\n";
  }

  return 0;
}

Compilation message (stderr)

passport.cpp: In function 'void build(int, int, int)':
passport.cpp:22:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
passport.cpp: In function 'void upd(int, int, int, int, int, int)':
passport.cpp:32:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
passport.cpp: In function 'int32_t main()':
passport.cpp:76:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     freopen("test.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:77:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     freopen("test.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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