Submission #1217549

#TimeUsernameProblemLanguageResultExecution timeMemory
1217549noyancanturkPassport (JOI23_passport)C++20
40 / 100
2095 ms1114112 KiB
#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define pb push_back

using pii=pair<int,int>;

const int lim=2e5+100;

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int n,q;
  cin>>n;
  int a[n],b[n];
  for(int i=0;i<n;i++){
    cin>>a[i]>>b[i];
    a[i]--,b[i]--;
  }
  cin>>q;
  int c[q];
  for(int i=0;i<q;i++){
    cin>>c[i];
    c[i]--;
  }
  for(int cur:c){
    int dp[n][n]{};
    dp[a[cur]][b[cur]]=1;
    queue<pii>pq;
    pq.push({a[cur],b[cur]});
    while(pq.size()){
      auto[l,r]=pq.front();
      pq.pop();
      for(int j=l;j<=r;j++){
        int L=min(l,a[j]),R=max(r,b[j]);
        if(!dp[L][R]){
          dp[L][R]=dp[l][r]+1;
          pq.push({L,R});
        }
      }
    }
    if(dp[0][n-1])cout<<dp[0][n-1]<<'\n';
    else cout<<"-1\n";
  }
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...