제출 #821709

#제출 시각아이디문제언어결과실행 시간메모리
821709thimote75철로 (IOI14_rail)C++14
30 / 100
46 ms588 KiB
#include "rail.h" #include <bits/stdc++.h> using namespace std; using idata = vector<int>; using bdata = vector<bool>; template<typename T> using lpq = priority_queue<T, vector<T>, greater<T>>; using ii = pair<int, int>; idata distance0; const int DTYPE = 2; const int CTYPE = 1; void findLocation(int N, int first, int location[], int stype[]) { location[0] = first; stype [0] = 1; distance0.resize(N, -1); int minD = 1e9; int minP = -1; for (int i = 1; i < N; i ++) { distance0[i] = getDistance(0, i); if (distance0[i] >= minD) continue ; minD = distance0[i]; minP = i; } int lefD = minP; int rigD = minP; location[minP] = first + minD; stype [minP] = DTYPE; int lefC = -1; lpq<ii> queue; for (int i = 1; i < N; i ++) if (i != minP) queue.push({ distance0[i], i }); while (queue.size() != 0) { const auto nextDP = queue.top(); queue.pop(); int next = nextDP.second; int nextDist = getDistance(lefD, next); int offDist = nextDist + minD; int resDist = distance0[next]; if (resDist == offDist) { bool isLefC = true; int passDist; if (lefC != -1) { passDist = getDistance(lefC, next); int offpDist = passDist + distance0[lefC]; isLefC = resDist < offpDist; } if (isLefC) { lefC = next; location[next] = first + minD - nextDist; stype [next] = CTYPE; } else { location[next] = passDist + location[lefC]; stype [next] = DTYPE; } } else { bool isRigD; int passDist = getDistance(rigD, next); int offpDist = passDist + distance0[rigD]; isRigD = resDist < offpDist; if (isRigD) { rigD = next; location[next] = first + distance0[next]; stype [next] = DTYPE; } else { location[next] = location[rigD] - passDist; stype [next] = CTYPE; } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...