Submission #1217549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217549		noyancanturk	Passport (JOI23_passport)	C++20	40 / 100	2095 ms	1114112 KiB

passport

#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";
  }
}

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