Submission #782358

#	Time	Username	Problem	Language	Result	Execution time	Memory
782358		AmirElarbi	Passport (JOI23_passport)	C++14	48 / 100	34 ms	3412 KiB

passport

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define INF 1e9
#define ve vector
#define vi ve<int>
#define ii pair<int,int>
#define vii ve<ii>
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace __gnu_pbds;
using namespace std;
const int nax = 1e5+5;
const int kax = 25+5;
const int MOD = 1e9+7;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int r[nax], l[nax], ans[nax], ansl[nax], ansr[nax];
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> l[i] >> r[i];
    queue<int> ql, qr;
    memset(ansl, -1, sizeof ansl);
    memset(ansr, -1, sizeof ansr);
    memset(ans, -1, sizeof ans);
    for (int i = 1; i <= n; ++i)
    {
        if(l[i] == 1){
            ansl[i] = 1; 
            ql.push(i);            
        } 
        if(r[i] == n){
            ansr[i] = 1; 
            qr.push(i);            
        } 
    }
    while(!ql.empty()){
        int u = ql.front();
        ql.pop();
        for (int i = 1; i <= n; ++i)
        {
            if(ansl[i] == -1 && l[i] <= u && u <= r[i]){
                ansl[i] = ansl[u]+1;
                ql.push(i);
            }
        }
    }
    while(!qr.empty()){
        int u = qr.front();
        //cout << u << endl;
        qr.pop();
        if(ansl[u] != -1) ans[u] = ansl[u] + ansr[u] - 1;
        for (int i = 1; i <= n; ++i)
        {
            if(ansr[i] == -1 && l[i] <= u && u <= r[i]){
                ansr[i] = ansr[u]+1;
                qr.push(i);
            }
        }
    }
    vii gt;
    for (int i = 1; i <= n; ++i)
    {
        if(ans[i] != -1) gt.pb({ans[i], i});
    }
    sort(gt.begin(), gt.end());
    for (auto x : gt)
    {
        for (int j = 1; j <= n; ++j)
        {
            if(l[j] <= x.se && x.se <= r[j]) ans[j] = min(ans[x.se]+1, ans[j]);
        }
    }
    int q;
    cin >> q;
    while(q--){
        int x;
        cin >> x;
        cout << ans[x] << endl;
    }
}

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