Submission #1192425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192425		epicci23	Passport (JOI23_passport)	C++20	48 / 100	884 ms	1114112 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 = 2505;

vector<array<int,3>> v[N][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];
  }
  
  vector<vector<int>> dist(n, vector<int>(n, INF));
  
  for(int i = 0; i < n; i++){
  	int left = -1, right = -1;
  	for(int j = i; j < n; j++){

  	  if(left == -1 || L[j] < L[left]) left = j;
  	  if(right == -1 || R[j] > R[right]) right = j;
      
      v[L[left]][j].push_back({i, j, 1});
      v[i][R[right]].push_back({i, j, 1});

  	  if(i == j){
  	    v[L[i]][R[i]].push_back({i, i, 1});
  	  }
  	  if(i < j){
  	  	v[i + 1][j].push_back({i, j, 0});
  	  	v[i][j - 1].push_back({i, j, 0});
  	  }
  	}
  }
  
  dist[0][n-1] = 0;
  deque<array<int,2>> dq;
  dq.push_back({0, n - 1});

  while(!dq.empty()){
  	int l = dq.front()[0], r = dq.front()[1];
  	dq.pop_front();

  	for(auto [x, y, w] : v[l][r]){
  	  if(w == 0 && dist[l][r] < dist[x][y]){
  	  	dist[x][y] = dist[l][r];
  	  	dq.push_front({x, y});
  	  }
  	  else if(w == 1 && dist[l][r] + 1 < dist[x][y]){
  	  	dist[x][y] = dist[l][r] + 1;
        dq.push_back({x, y});
  	  }
  	}
  }

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

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

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