oj.uz

Submission #63109

# Submission time Handle Problem Language Result Execution time Memory
63109 2018-07-31T18:26:40 Z Arturgo Railway Trip (JOI17_railway_trip) C++11
100 / 100
 1655 ms 257072 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 42744 KB Output is correct
2 Correct 38 ms 42864 KB Output is correct
3 Correct 39 ms 42864 KB Output is correct
4 Correct 39 ms 42880 KB Output is correct
5 Correct 40 ms 42932 KB Output is correct
6 Correct 42 ms 43044 KB Output is correct
7 Correct 50 ms 43104 KB Output is correct
8 Correct 48 ms 43224 KB Output is correct
9 Correct 44 ms 43224 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 44544 KB Output is correct
2 Correct 727 ms 151812 KB Output is correct
3 Correct 716 ms 165560 KB Output is correct
4 Correct 744 ms 176428 KB Output is correct
5 Correct 701 ms 181336 KB Output is correct
6 Correct 745 ms 187396 KB Output is correct
7 Correct 835 ms 189060 KB Output is correct
8 Correct 139 ms 189060 KB Output is correct
9 Correct 405 ms 189060 KB Output is correct
10 Correct 230 ms 189060 KB Output is correct
11 Correct 649 ms 189060 KB Output is correct
12 Correct 545 ms 189060 KB Output is correct
13 Correct 627 ms 189060 KB Output is correct
14 Correct 665 ms 189060 KB Output is correct
15 Correct 547 ms 189060 KB Output is correct
16 Correct 491 ms 189060 KB Output is correct
17 Correct 788 ms 194224 KB Output is correct
18 Correct 893 ms 194752 KB Output is correct
19 Correct 619 ms 195940 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1254 ms 195940 KB Output is correct
2 Correct 1086 ms 195940 KB Output is correct
3 Correct 1201 ms 195940 KB Output is correct
4 Correct 1444 ms 195940 KB Output is correct
5 Correct 1262 ms 195940 KB Output is correct
6 Correct 1408 ms 195940 KB Output is correct
7 Correct 1175 ms 195940 KB Output is correct
8 Correct 572 ms 195940 KB Output is correct
9 Correct 274 ms 195940 KB Output is correct
10 Correct 232 ms 195940 KB Output is correct
11 Correct 249 ms 195940 KB Output is correct
12 Correct 244 ms 195940 KB Output is correct
13 Correct 229 ms 195940 KB Output is correct
14 Correct 390 ms 195940 KB Output is correct
15 Correct 437 ms 195940 KB Output is correct
16 Correct 838 ms 195940 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1305 ms 218812 KB Output is correct
2 Correct 1560 ms 220720 KB Output is correct
3 Correct 1655 ms 222220 KB Output is correct
4 Correct 1458 ms 223852 KB Output is correct
5 Correct 247 ms 223852 KB Output is correct
6 Correct 885 ms 223852 KB Output is correct
7 Correct 910 ms 223852 KB Output is correct
8 Correct 749 ms 223852 KB Output is correct
9 Correct 1098 ms 223852 KB Output is correct
10 Correct 1042 ms 223852 KB Output is correct
11 Correct 1128 ms 223852 KB Output is correct
12 Correct 1164 ms 223852 KB Output is correct
13 Correct 1166 ms 223852 KB Output is correct
14 Correct 1157 ms 223852 KB Output is correct
15 Correct 1278 ms 223852 KB Output is correct
16 Correct 1474 ms 246912 KB Output is correct
17 Correct 1104 ms 246912 KB Output is correct
18 Correct 1115 ms 246912 KB Output is correct
19 Correct 1221 ms 246912 KB Output is correct
20 Correct 1278 ms 246912 KB Output is correct
21 Correct 1086 ms 252980 KB Output is correct
22 Correct 1342 ms 254640 KB Output is correct
23 Correct 1240 ms 257072 KB Output is correct