Submission #1278624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278624		sasde	Passport (JOI23_passport)	C++20	48 / 100	698 ms	333276 KiB

passport

#include<bits/stdc++.h>
using namespace std;
bool M1;
#define PI 3.14159265358979323846
#define sz(a) (int)a.size()
#define all(x) x.begin(),x.end()
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define emf emplace_front
#define em emplace
const int N=2505+5,inf=1e9;
int node,l[N],r[N],query,dp[N*N],minl[N][N],maxr[N][N];
vector<ii>ver[N*N];
int idx(int u,int v){
    return (u-1)*node+v;
}
void build(){
     for(int j=1;j<=node;++j)
        for(int k=1;k<=node;++k)dp[idx(j,k)]=inf;
        dp[idx(1,node)]=0;
        deque<int>p;
        p.push_front(idx(1,node));
        for(int i=1;i<=node;++i){
            for(int j=i;j<=node;++j){
                ver[idx(i,maxr[i][j])].emb(idx(i,j),1);
                ver[idx(minl[i][j],j)].emb(idx(i,j),1);
                if(i==j)ver[idx(l[i],r[i])].emb(idx(i,j),1);
                else{
                    ver[idx(i+1,j)].emb(idx(i,j),0);
                    ver[idx(i,j-1)].emb(idx(i,j),0);
                }
            }
        }
        while(!p.empty()){
            int u=p.front();
            // cout <<x.fi<<" "<<x.se<<'\n';
            // cout <<u<<'\n';
            p.pop_front();
            for(auto v:ver[u]){
                if(dp[v.fi]>dp[u]+v.se){
                    dp[v.fi]=dp[u]+v.se;
                    if(v.se==1)
                    p.emb(v.fi);
                    else p.emf(v.fi);
                }
            }

        }
}
bool M2;
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> node;
    for(int i=1;i<=node;++i)cin >> l[i] >> r[i];
    for(int i=1;i<=node;++i){
        minl[i][i]=l[i];
        maxr[i][i]=r[i];
        for(int j=i+1;j<=node;++j){
            minl[i][j]=min(minl[i][j-1],l[j]);
            maxr[i][j]=max(maxr[i][j-1],r[j]);
        }
    }
    build();
    cin >> query;
    while(query--){
        int i;
        cin >> i;
        cout<<(dp[idx(i,i)]==inf?-1:dp[idx(i,i)])<<'\n';
    }
    cerr <<abs(&M1-&M2)/1024.0/1024.0<<" MB\n";
}

Compilation message (stderr)

passport.cpp:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   62 | main()
      | ^~~~

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