Submission #63109

#	Time	Username	Problem	Language	Result	Execution time	Memory
63109		Arturgo	Railway Trip (JOI17_railway_trip)	C++11	100 / 100	1655 ms	257072 KiB

railway_trip

#include <vector>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <ctime>
using namespace std;

const int INFINI = 1000 * 1000 * 1000;

struct Inter {
  int chaine, dist;
  int nums[2];
  Inter() {
    chaine = INFINI;
    nums[0] = nums[1] = -1;
    dist = INFINI;
  }

  void push(int _chaine, int _num, int _dist) {
    if(_dist < dist) {
      dist = _dist;
      chaine = _chaine;
      nums[0] = _num;
      nums[1] = -1;
    }
    else if(_dist == dist) {
      if(nums[0] != _num) {
	nums[1] = _num;
      }
    }
  }
};

int nbStations, nbTypes, nbReqs;

int hauteur[100 * 1000];
int suiv[100 * 1000], prec[100 * 1000];

void calculeTransitions() {
  vector<int> ids;

  for(int iStation = 0;iStation < nbStations;iStation++) {
    while(!ids.empty() && hauteur[ids.back()] < hauteur[iStation]) {
      suiv[ids.back()] = iStation;
      ids.pop_back();
    }

    if(ids.empty()) {
      prec[iStation] = -1;
    }
    else {
      prec[iStation] = ids.back();
    }

    while(!ids.empty() && hauteur[ids.back()] == hauteur[iStation]) {
      suiv[ids.back()] = iStation;
      ids.pop_back();
    }

    ids.push_back(iStation);
  }

  while(!ids.empty()) {
    suiv[ids.back()] = -1;
    ids.pop_back();
  }
}

vector<vector<int>> chaines;
vector<int> fils[100 * 1000];
vector<int> parent;

int chaine[100 * 1000];

int cur_event = 0;
int in[100 * 1000], out[100 * 1000];

void calculeInters(int chaine = 0) {
  in[chaine] = cur_event++;

  for(int suiv : fils[chaine]) {
    calculeInters(suiv);
  }

  out[chaine] = cur_event++;
}

bool estFils(int a, int b) {
  return in[b] <= in[a] && out[a] <= out[b];
}

void calculeChaines() {
  vector<pair<int, int>> stations;
  int cur_chaine[100 * 1000];

  cur_chaine[0] = 0;
  parent.push_back(-1);
  chaines.push_back({0});

  for(int iStation = 1;iStation < nbStations;iStation++) {
    cur_chaine[iStation] = -1;
    stations.push_back({hauteur[iStation], iStation});
  }

  sort(stations.begin(), stations.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
     if(a.first != b.first)
	return a.first > b.first;
     return a.second < b.second;
  });

  for(pair<int, int> station : stations) {
    int id = station.second;
    if(hauteur[prec[id]] != hauteur[id]) {
      int cur_parent = cur_chaine[prec[id]];
      cur_chaine[prec[id]] = chaines.size();
      cur_chaine[id] = chaines.size();
      chaine[id] = chaines.size();
      fils[cur_parent].push_back(chaines.size());
      chaines.push_back({prec[id], id});
      parent.push_back(cur_parent);
    }
    else {
      cur_chaine[id] = cur_chaine[prec[id]];
      chaine[id] = cur_chaine[id];
      chaines[chaine[id]].push_back(id);
    }

    if(suiv[id] != -1 && hauteur[suiv[id]] != hauteur[id]) {
      chaines[chaine[id]].push_back(suiv[id]);
    }
  }
}

vector<Inter> remontes[17][100 * 1000];

inline int getNum(int chaine, int elem) {
  return lower_bound(chaines[chaine].begin(), chaines[chaine].end(), elem) - chaines[chaine].begin();
}

inline Inter remonte(Inter& bests, int hauteur) {
  Inter coords;

  for(int iNumD = 0;iNumD < 2;iNumD++) {
    int numD = bests.nums[iNumD];
    if(numD == -1) continue;
    
    Inter bestsS = remontes[hauteur][bests.chaine][numD];
    for(int iNumS = 0;iNumS < 2;iNumS++) {
      int numS = bestsS.nums[iNumS];
      if(numS == -1) continue;
      coords.push(bestsS.chaine, numS, bestsS.dist + bests.dist);
    }
  }
  
  return coords;
}

inline void calculeBests() {
  for(int iChaine = 0;iChaine < (int)chaines.size();iChaine++) {
    vector<int> cur_chaine = chaines[iChaine];
    
    for(int iElem = 0;iElem < (int)cur_chaine.size();iElem++) {
      Inter coords;
      if(parent[iChaine] == -1) {
	coords.push(iChaine, iElem, 0);
	remontes[0][iChaine].push_back(coords);
      }
      else {
	coords.push(parent[iChaine], getNum(parent[iChaine], cur_chaine[0]), iElem);
	coords.push(parent[iChaine], getNum(parent[iChaine], cur_chaine.back()), cur_chaine.size() - iElem - 1);
	remontes[0][iChaine].push_back(coords);
      }
    }
  }
  
  for(int iHauteur = 1;iHauteur < 17;iHauteur++) {
    for(int iChaine = 0;iChaine < (int)chaines.size();iChaine++) {
      vector<int> cur_chaine = chaines[iChaine];
      for(int iElem = 0;iElem < (int)cur_chaine.size();iElem++) {
	Inter coords = remonte(remontes[iHauteur - 1][iChaine][iElem], iHauteur - 1);
	remontes[iHauteur][iChaine].push_back(coords);
      }
    }
  }
}

inline Inter remonteJusque(Inter deb, int chaine) {
  if(estFils(chaine, deb.chaine))
    return deb;
  Inter cur = deb;
  for(int iHauteur = 16;iHauteur >= 0;iHauteur--) {
    Inter rem = remonte(cur, iHauteur);
    if(!estFils(chaine, rem.chaine)) {
      cur = rem;
    }
  }
  return remonte(cur, 0);
}

inline int modulo(int a, int mod) {
  return (((a % mod) + mod) % mod);
}

inline int distMod(int a, int b, int mod) {
  return min(modulo(a - b, mod), mod - modulo(a - b, mod));
}

inline int distEntre(int deb, int fin) {
  Inter debCoord;
  debCoord.push(chaine[deb], getNum(chaine[deb], deb), 0);
  
  Inter finCoord;
  finCoord.push(chaine[fin], getNum(chaine[fin], fin), 0);

  Inter bestsDeb = remonteJusque(debCoord, chaine[fin]);
  Inter bestsFin = remonteJusque(finCoord, chaine[deb]);

  int minDist = 1000 * 1000;
  for(int iNumD = 0;iNumD < 2;iNumD++) {
    int numD = bestsDeb.nums[iNumD];
    if(numD == -1) continue;
    
    for(int iNumF = 0;iNumF < 2;iNumF++) {
      int numF = bestsFin.nums[iNumF];
      if(numF == -1) continue;
      
      if(bestsDeb.chaine == 0) {
	minDist = min(minDist, bestsDeb.dist + bestsFin.dist + abs(numD - numF));
      }
      else {
	minDist = min(minDist, bestsDeb.dist + bestsFin.dist + distMod(numD, numF, chaines[bestsDeb.chaine].size()));
      }
    }
  }
  
  return minDist;
}

int main() {
  scanf("%d%d%d", &nbStations, &nbTypes, &nbReqs);

  for(int iStation = 0;iStation < nbStations;iStation++) {
    scanf("%d", &hauteur[iStation]);
    hauteur[iStation]--;
  }

  calculeTransitions();
  calculeChaines();
  calculeInters();
  calculeBests();
  
  for(int iReq = 0;iReq < nbReqs;iReq++) {
    int deb, fin;
    scanf("%d%d", &deb, &fin);
    deb--; fin--;
    printf("%d\n", distEntre(deb, fin) - 1);
  }
  return 0;
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:240:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &nbStations, &nbTypes, &nbReqs);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:243:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &hauteur[iStation]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:254:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &deb, &fin);
     ~~~~~^~~~~~~~~~~~~~~~~~~~

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