Submission #961898

#	Time	Username	Problem	Language	Result	Execution time	Memory
961898		anton	Passport (JOI23_passport)	C++17	48 / 100	2127 ms	1048576 KiB

passport

#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>
#define int long long

const int MAX_N =2501;
const int INF=  1e9;
pii inter[MAX_N];
int dist[MAX_N][MAX_N];
int dp[2][MAX_N];
vector<int> radj[MAX_N];
vector<int> begins[2];
int n;


void BFS(int id){
    queue<pii> q;
    set<int> s;
    for(int i = 0; i<n; i++){
        s.insert(i);
    }
    s.erase(id);
    dist[id][id] = 0;
    q.push({id, 0});

    while(q.size()>0){
        int cur= q.front().first;
        int cur_dist = q.front().second;
        //cout<<cur<<" "<<cur_dist<<endl;
        q.pop();
        for(auto it = s.lower_bound(inter[cur].first); it!=s.upper_bound(inter[cur].second);){
            int i = *it;
    
            dist[id][i]  = cur_dist+1;
            q.push({i, cur_dist+1});
            s.erase(it++);
            
        }
    }
}

void precalc_dist(){
    for(int i = 0; i<n; i++){
        for(int j = 0; j<n; j++)dist[i][j] = INF;
        BFS(i);
    }
}
signed main(){
    cin>>n;

    for(int i = 0; i<n; i++){
        cin>>inter[i].first>>inter[i].second;
        inter[i].first--;
        inter[i].second--;
        for(int j = inter[i].first; j<=inter[i].second; j++){
            radj[j].push_back(i);
        }
        if(inter[i].first==0){
            begins[0].push_back(i);
        }
        if(inter[i].second == n-1){
            begins[1].push_back(i);
        }
    }
    
    
    int q;
    cin>>q;
    precalc_dist();
    for(int c= 0; c<2; c++){
        for(int i = 0; i<n; i++){
            dp[c][i] = INF;
            for(auto e: begins[c]){
                //cout<<c<<" "<<i<<" "<<e<<" "<<dist[i][e]+1<<endl;
                dp[c][i] = min(dp[c][i], dist[i][e]+1);
            }
        }
    }

    for(int i = 0; i<q; i++){
        int v;
        cin>>v;
        v--;
        int res= INF;
        int mid= v;
        for(int j = 0; j<n; j++){
            //cout<<dist[v][j]<<end
            if(dp[0][j]-1 + dp[1][j] + dist[v][j]<res){
                //cout<<v<<" "<<j<<endl;
                //cout<<dpr.tr[j+dpr.sz]<<" "<<dpl.tr[j+dpl.sz]<<" "<<dist[v][j]<<endl;
                mid= j;
            }
            res= min(res, dp[0][j]-1 + dp[1][j] + dist[v][j]);
            
        }
        if(res>=INF){
            cout<<-1<<endl;
        }
        else{
            cout<<res<<" "<<endl;
        }
    }
}

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:86:13: warning: variable 'mid' set but not used [-Wunused-but-set-variable]
   86 |         int mid= v;
      |             ^~~

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