Submission #1085895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085895		Bananabread	Passport (JOI23_passport)	C++17	0 / 100	83 ms	196176 KiB

passport

#include<bits/stdc++.h>
#define ll long long
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname ""
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
vector<array<int,3>> adj[2501][2501];
ll dist[2501][2501];
ll vis[2501][2501];
ll n,q;
ll l[2501];
ll r[2501];
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //frep;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
    }
    for(int i=1;i<=n;i++){
        ll mx=0,mn=1e18;
        for(int j=1;j<=n;j++){
            mx=max(mx,r[i]);
            mn=min(mn,l[i]);
            if(i==j) adj[mn][mx].push_back({i,j,1});
            adj[mn][j].push_back({i,j,1});
            adj[i][mx].push_back({i,j,1});
            if(i!=j){
                adj[i+1][j].push_back({i,j,0});
                adj[i][j-1].push_back({i,j,0});
            }
        }
    }
    memset(dist,0x3f,sizeof(dist));
    dist[1][n]=0;
    deque<array<ll,2>> dq;
    dq.push_front({1,n});
    while(!dq.empty()){
        ll u=dq.front()[0],v=dq.front()[1];
        dq.pop_front();
        if(vis[u][v]) continue;
        vis[u][v]=1;
        for(auto i:adj[u][v]){
            ll x=i[0],y=i[1],w=i[2];
            if(dist[x][y]>dist[u][v]+w){
                dist[x][y]=dist[u][v]+w;
                if(w==0){
                    dq.push_front({x,y});
                }
                else{
                    dq.push_back({x,y});
                }
            }
        }
    }
    cin>>q;
    for(int i=1;i<=q;i++){
        ll x;
        cin>>x;
        cout<<(dist[x][x] >= 1e18 ? -1 : dist[x][x])<<ntr;
    }
}

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