Submission #1064930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064930		oscar1f	Railway Trip (JOI17_railway_trip)	C++17	20 / 100	2064 ms	12632 KiB

railway_trip

#include<bits/stdc++.h>
using namespace std;

//#define int long long

const int TAILLE_MAX=100*1000+5,INFINI=1000*1000*1000;
int nbVal,typeMaxi,nbReq;
int val[TAILLE_MAX];
vector<int> posVal[TAILLE_MAX];
set<int> plusGrand;
set<int>::iterator it;
int vois[TAILLE_MAX][2];
int dist[TAILLE_MAX][2];

void calcDist(int deb,int tab) {
    for (int i=1;i<=nbVal;i++) {
        dist[i][tab]=INFINI;
    }
    deque<int> enCours;
    enCours.push_back(deb);
    int longueur,pos,distCour=0;
    while (!enCours.empty()) {
        longueur=enCours.size();
        for (int i=0;i<longueur;i++) {
            pos=enCours.front();
            enCours.pop_front();
            if (dist[pos][tab]==INFINI) {
                dist[pos][tab]=distCour;
                for (int j=0;j<2;j++) {
                    if (vois[pos][j]!=0) {
                        enCours.push_back(vois[pos][j]);
                    }
                }
            }
        }
        distCour++;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbVal>>typeMaxi>>nbReq;
    for (int i=1;i<=nbVal;i++) {
        cin>>val[i];
        posVal[val[i]].push_back(i);
    }
    plusGrand.insert(-INFINI);
    plusGrand.insert(INFINI);
    for (int i=typeMaxi;i>=1;i--) {
        for (int j:posVal[i]) {
            plusGrand.insert(j);
        }
        for (int j:posVal[i]) {
            it=plusGrand.lower_bound(j);
            it++;
            if (abs((*it))!=INFINI) {
                vois[j][1]=(*it);
            }
            it--;
            it--;
            if (abs((*it))!=INFINI) {
                vois[j][0]=(*it);
            }
        }
    }
    int deb,fin,rep;
    for (int ireq=0;ireq<nbReq;ireq++) {
        cin>>deb>>fin;
        calcDist(deb,0);
        calcDist(fin,1);
        rep=INFINI;
        for (int i=1;i<=nbVal;i++) {
            rep=min(rep,dist[i][0]+dist[i][1]);
        }
        cout<<rep-1<<"\n";
    }
    return 0;
}
 

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55