According to many researches, people can stand on a bus for several hours, but w

Question

According to many researches, people can stand on a bus for several hours, but waiting for a bus for more than 30 minutes at a bus station can make us exhausted. The Chef is a perfect example for this fact. He always tries to reduce the longest period of time of waiting for a bus. Therefore, optimizing the traveling plan for him is far from an easy task.

Let's consider the bus system with N bus stations (numbered from 1 to N) and M buses (numbered from 1 to M). Each bus is represented by 4 integer numbers U, V, S, E which means it will start at the bus station U at the time S and arrive at the bus station V at the time E with no intermediate bus stations. If passenger arrives at the bus station U at the time X %u2264 S, he has to wait for S %u2212 X units of time to catch this bus. Note, that if he arrives at the bus station U exactly at time S he can catch this bus with no waiting time.

The Chef starts at the time 0 in the bus station 1, and he wants to arrive at the bus station N in a way that the longest period that he spends for waiting for a bus is as small as possible. Besides, he must be at the bus station N before or at the time T for a specially important meeting. Note, that he may wait for a meeting if he arrives at the bus station N early but that period is not our concern here, since he doesn't wait for any bus at that time.

The first line of the input contains three space-separated integers N, T and M, denoting the number of bus stations, the deadline for coming to bus station N and the number of buses, respectively. Each of the following M lines contains four space-separated integers U, V, S, E, the parameters of the current bus as described in the problem statement.

If Chef cannot arrive at the bus station N before or at the time T, output -1. Otherwise, output the maximum period of time he has to wait for a bus in the optimal traveling plan.

There are three different traveling plans:

For each traveling plan Chef arrives at the bus station N = 5 before the time T = 10. But only the first traveling plan is optimal, since the longest period of time his has to wait is 2.

Explanation / Answer

#include <cstdio> #include <deque> #include <algorithm> struct Bus { int x, y; int t1, t2; bool operator< (Bus const & o) const { return t1 < o.t1; } } edge[100005]; int perm[100005]; bool by_endtime(int i, int j) { return edge[i].t2 < edge[j].t2; } struct t_and_v { int t; int v; t_and_v (int t, int v) : t (t), v (v) { } }; const int infInt = 1010101010; int opt[100005]; // i -> min. wait time over all sequences ending with bus #i inline int T(int i) { return edge[i].t2; } inline int V(int i) { return opt[i]; } int memory[100005]; int * ql[50005], * qr[50005]; int latest[50005]; inline void push(int i) { int k = edge[i].y; int t = T(i), v = V(i); if (ql[k]!=qr[k] and T(*(qr[k]-1)) == t and V(*(qr[k]-1)) <= v) { return; } while (ql[k]!=qr[k] and V(*(qr[k]-1)) >= v) qr[k] --; *qr[k] = i; qr[k] ++; } inline int get(int k, int t) { while (ql[k]!=qr[k] and T(*ql[k]) + V(*ql[k]) < t) { latest[k] = T(*ql[k]); ql[k] ++; } int answer = std::min(infInt, t - latest[k]); if (ql[k]!=qr[k]) answer = std::min(answer, V(*ql[k])); return answer; } int main() { int n, T, ne; scanf("%d%d%d", &n, &T, &ne); for (int i = 0; i < ne; i ++) { int u, v, s, e; scanf("%d%d%d%d", &u, &v, &s, &e); edge[i].x = u; edge[i].y = v; edge[i].t1 = s; edge[i].t2 = e; perm[i] = i; } std::sort(edge, edge + ne); std::sort(perm, perm + ne, by_endtime); static int need[50005]; for (int i=1;i<=n;i++)latest[i]=-infInt; for (int i=1;i<=n;i++)need[i]=0; for (int edgeID=0; edgeID<ne; edgeID++) { need[edge[edgeID].y] ++; } int ptr = 0; for (int i=1;i<=n;i++) { ql[i] = qr[i] = memory + ptr; ptr += need[i]; } latest[1] = 0; int answer = infInt; int perm_ptr=0; for (int edgeID=0; edgeID<ne; edgeID++) { Bus & b (edge[edgeID]); while (perm_ptr<ne and edge[perm[perm_ptr]].t2<=b.t1) { int i=perm[perm_ptr]; push(i); perm_ptr++; } opt[edgeID] = get(b.x, b.t1); if (b.y == n and b.t2 <= T) { answer = std::min(answer, opt[edgeID]); } } if (answer > T) puts("-1"); else printf("%d ", answer); }

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.