제출 #1257378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257378		notisora	Passport (JOI23_passport)	C++20	0 / 100	9 ms	19032 KiB

passport

///NotIsora
///This is my last dance
#include<bits/stdc++.h>
#define modulo 1000000007
#define fi first
#define se second
#define sq(x) (x)*(x)
#define ll long long
#define ld long double
#define el '\n'
#define pb push_back
///#define int long long

using namespace std;

const int N=2e5+5;
vector<int>st[N*4];
int n,q;
int ans[N];

struct Passport{
    int l,r,idx;
    bool operator < (const Passport&other) const{
        if (l==other.l) return r<other.r;
        return l<other.l;
    }
};
Passport arr[N];

void update(int u,int v,int val,int node=1,int l=1,int r=n){
    if (u>r || l>v) return;
    if (u<=l && r<=v){
        st[node].pb(val);
        return;
    }
    int m=(l+r)>>1;
    update(u,v,val,node*2,l,m);
    update(u,v,val,node*2+1,m+1,r);
}

void dijkstra(vector<int>&d){

    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    vector<bool>vis(n*4,0);
    for(int i=1;i<=n;i++){
        if (d[i]>=1e8) continue;
        pq.push({d[i],i});
    }

    while(!pq.empty()){
        int dis=pq.top().fi;
        int pos=pq.top().se;
        pq.pop();
        if (dis>d[pos]) continue;

        int node=1,l=1,r=n;
        while(16032008){
            if (!vis[node]){

                for(int&u:st[node]){
                    if (d[u]>dis+1){
                        d[u]=dis+1;
                        pq.push({d[u],u});
                    }
                }
            }
            if (l==r) break;
            int m=(l+r)>>1;
            if (pos<=m){
                node*=2;
                r=m;
            }
            else{
                node=node*2+1;
                l=m+1;
            }
        }
    }
}

signed main(){
//    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("i.INP","r",stdin);
    cin>>n;
    vector<int>dL(n+1,1e8),dR(n+1,1e8),dp(n+1,1e8);

    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        arr[i]={l,r,i};
        update(l,r,i);
    }

    dL[1]=0;
    dR[n]=0;

    dijkstra(dL);
    dijkstra(dR);

    for(int i=1;i<=n;i++){
        dp[i]=dL[i]+dR[i];
        if (arr[i].l==1 && arr[i].r==n) dp[i]=1;
    }
    dijkstra(dp);

    int q;
    cin>>q;
    while(q--){
        int z;
        cin>>z;
        if (dp[z]>=1e8) cout<<-1;
        else cout<<dp[z];
        cout<<el;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

passport.cpp: In function 'int main()':
passport.cpp:83:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     freopen("i.INP","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~

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