제출 #1222117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222117		Aviansh	Passport (JOI23_passport)	C++20	40 / 100	2093 ms	1114112 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--){
        int dists[n][n];
        for(int i = 0;i<n;i++){
            fill(dists[i],dists[i]+n,1e9);
        }
        int x;
        cin >> x;
        x--;
        dists[rangs[x][0]][rangs[x][1]]=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]][nx[1]]==1e9){
                    dists[nx[0]][nx[1]]=dists[curr[0]][curr[1]]+1;
                    q.push(nx);
                }
            }
        }
        if(dists[0][n-1]==1e9){
            cout << -1 << "\n";
        }
        else{
            cout << dists[0][n-1] << "\n";
        }
    }
    return 0;
}

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