Submission #997898

#	Time	Username	Problem	Language	Result	Execution time	Memory
997898		Otalp	Railway Trip 2 (JOI22_ho_t4)	C++14	8 / 100	2100 ms	19024 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define ld long double
#define pb push_back

pii a[200100];
pii c[200100];
int dp[200100], us[200100];
vector<int> dq[200100];
pii ddp[200100][20][20];


void solve(){
    int n, k;
    cin>>n>>k;
    int m;

    cin>>m;
    
    for(int i=1; i<=m; i++){
        cin>>a[i].ff>>a[i].ss;
        if(a[i].ff < a[i].ss){
            dq[a[i].ff].pb(a[i].ss);
            dq[min(a[i].ff + k, a[i].ss + 1)].pb(-a[i].ss);
        }
        if(a[i].ff > a[i].ss){
            dq[max(a[i].ff - k + 1, a[i].ss)].pb(a[i].ss);
            dq[a[i].ff + 1].pb(-a[i].ss);
        }
    }
    multiset<int> dd;
    for(int i=1; i<=n; i++){
        //cout<<"##############\n";
        //cout<<i<<'\n';
        for(int h: dq[i]){
            //cout<<h<<' ';
            if(h > 0) dd.insert(h);
            else dd.erase(dd.find(-h));
        }
        //cout<<'\n';
        int l=i, r=i;
        if(dd.size()){
            l = min(l, *dd.begin());
            r = max(r, *dd.rbegin());
        }
        c[i] = {l, r};
    }
    //for(int i=1; i<=n; i++){
        //cout<<c[i].ff<<' '<<c[i].ss<<'\n';
    //}
    int t;
    cin>>t;
    while(t--){
        int s, f;
        cin>>s>>f;
        queue<int> q;
        q.push(s);
        for(int i=1; i<=n; i++){
            dp[i] = us[i] = 0;
        }
        dp[s] = 0;
        us[s] = 1;
        while(q.size()){
            int v = q.front();
            q.pop();
            for(int i = c[v].ff; i<=c[v].ss; i++){
                if(us[i] == 1) continue;
                dp[i] = dp[v] + 1;
                q.push(i);
                us[i] = 1;
            }
        }
        if(us[f] == 0){
            cout<<-1<<'\n';
        }
        else{
            cout<<dp[f]<<'\n';    
        }
    }
}


signed main(){
    solve();
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13