답안 #63109 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63109	2018-07-31T18:26:40 Z	Arturgo	Railway Trip (JOI17_railway_trip)	C++11	100 / 100	1655 ms	257072 KB

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

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #63109

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 15.0 / 15.0

Subtask #3 25.0 / 25.0

Subtask #4 55.0 / 55.0

Subtask #1
5.0 / 5.0

Subtask #2
15.0 / 15.0

Subtask #3
25.0 / 25.0

Subtask #4
55.0 / 55.0