Submission #1192454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192454		epicci23	Passport (JOI23_passport)	C++20	100 / 100	495 ms	124984 KiB

passport

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int INF = 1e18;
const int N = 4e5 + 5;

vector<array<int,2>> v[N];

void _(){
  int n;
  cin >> n;

  int L[N], R[N];
  for(int i = 0; i < n; i++){
  	cin >> L[i] >> R[i];
  	--L[i], --R[i];
  }
  
  for(int i = n - 1; i; --i){
    v[i * 2].push_back({i, 0});
    v[i * 2 + 1].push_back({i, 0});
  }
  
  for(int i = 0; i < n; i++){
  	int l = L[i] + n, r = R[i] + n + 1;
  	for(; l < r; l >>= 1, r >>= 1){
  	  if(l&1) v[l++].push_back({i + n, 1});
  	  if(r&1) v[--r].push_back({i + n, 1});
  	}
  }
  
  vector<int> dist1(2 * N, INF), distn(2 * N, INF);

  dist1[n] = 0;
  priority_queue<array<int,2>,vector<array<int,2>>,greater<>> dq;
  dq.push({0, n});

  while(!dq.empty()){
    int c = dq.top()[1];
    int d = dq.top()[0];
    dq.pop();
    if(d > dist1[c]) continue;

    for(auto [u, w] : v[c]){
      if(w == 0 && dist1[c] < dist1[u]){
        dist1[u] = dist1[c];
        dq.push({dist1[u], u});
      }
      if(w == 1 && dist1[c] + 1 < dist1[u]){
      	dist1[u] = dist1[c] + 1;
      	dq.push({dist1[u], u});
      }
    }  
  }

  dist1[n] = 1;
  distn[2 * n - 1] = 0;
  dq.push({0, 2 * n - 1});

  while(!dq.empty()){
    int c = dq.top()[1];
    int d = dq.top()[0];
    dq.pop();
    if(d > distn[c]) continue;

    for(auto [u, w] : v[c]){
      if(w == 0 && distn[c] < distn[u]){
        distn[u] = distn[c];
        dq.push({distn[u], u});
      }
      if(w == 1 && distn[c] + 1 < distn[u]){
      	distn[u] = distn[c] + 1;
      	dq.push({distn[u], u});
      }
    }  
  }

  distn[2 * n - 1] = 1;

  vector<int> dist1n(2 * N, INF);
  for(int i = n; i < 2 * n; i++){
  	dist1n[i] = dist1[i] + distn[i] - 1;
  	dq.push({dist1n[i], i});
  }

  while(!dq.empty()){
    int d = dq.top()[0];
    int c = dq.top()[1];
    dq.pop();

    if(d > dist1n[c]) continue;

    for(auto [u, w] : v[c]){
      if(w == 0 && dist1n[c] < dist1n[u]){
        dist1n[u] = dist1n[c];
        dq.push({dist1n[u], u});
      }
      if(w == 1 && dist1n[c] + 1 < dist1n[u]){
      	dist1n[u] = dist1n[c] + 1;
      	dq.push({dist1n[u], u});
      }
    }  
  }

  int q;
  cin >> q;
  while(q--){
  	int c; cin >> c;
  	--c;
    if(dist1n[c + n] >= INF - 1) cout << -1 << '\n';
    else cout << dist1n[c + n] << '\n';
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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