제출 #1222122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222122		Aviansh	Passport (JOI23_passport)	C++20	16 / 100	2094 ms	11072 KiB

passport

#include <bits/stdc++.h>

using namespace std;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    array<int,2>rangs[n];
    for(int i = 0;i<n;i++){
        cin >> rangs[i][0];
        cin >> rangs[i][1];
        rangs[i][0]--;
        rangs[i][1]--;
        //inclusive range.
    }
    int q;
    cin >> q;
    while(q--){
        map<array<int,2>,int>dists;
        int x;
        cin >> x;
        x--;
        dists[rangs[x]]=1;
        queue<array<int,2>>q;
        q.push({rangs[x][0],rangs[x][1]});
        while(!q.empty()){
            array<int,2>curr = q.front();
            q.pop();
            for(int i = curr[0];i<=curr[1];i++){
                array<int,2>nx=curr;
                nx[0]=min(nx[0],rangs[i][0]);
                nx[1]=max(nx[1],rangs[i][1]);
                if(dists[nx]==0){
                    dists[nx]=dists[curr]+1;
                    q.push(nx);
                }
            }
        }
        if(dists[{0,n-1}]==0){
            cout << -1 << "\n";
        }
        else{
            cout << dists[{0,n-1}] << "\n";
        }
    }
    return 0;
}

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