Add solution to 2021 Dec Tickets

1 files changed, 79 insertions, 0 deletions

diff --git a/21/dec/tickets.cpp b/21/dec/tickets.cpp
new file mode 100644
index 0000000..cd6e006
--- /dev/null
+++ b/21/dec/tickets.cpp
@@ -0,0 +1,79 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+using pl = pair<ll, ll>;
+constexpr int MX = 1e5+5;
+
+int N, K;
+
+struct ticket_t {
+	int c, p, a, b;
+} T[MX];
+
+struct seg_tree {
+	int seg[4*MX];
+	inline int pull(const int & a, const int & b) { return max(a, b); }
+	void build(int l = 0, int r = MX-1, int n = 1) {
+		if (l == r) { seg[n] = T[l].b; return; }
+		int m = l+r>>1;
+		build(l, m, n<<1), build(m+1, r, n<<1|1);
+		seg[n] = pull(seg[n<<1], seg[n<<1|1]);
+	}
+	void remove(vector<int> & vc, int x, int l = 0, int r = MX-1, int n = 1) {
+		if (l >= K || T[l].a > x || seg[n] < x) return;
+		if (l == r) {
+			seg[n] = -1, vc.push_back(l);
+		}
+		else {
+			int m = l+r>>1;
+			remove(vc, x, l, m, n<<1), remove(vc, x, m+1, r, n<<1|1);
+			seg[n] = pull(seg[n<<1], seg[n<<1|1]);
+		}
+	}
+};
+
+void dijkstra(vector<ll> & dist) {
+	priority_queue<pl, vector<pl>, greater<>> pq;
+	for (int i = N; i < N+K; ++i)
+		dist[T[i-N].c] = min(dist[i]+T[i-N].p, dist[T[i-N].c]);
+	for (int i = 0; i < N; ++i) if (dist[i] < 1e18)
+		pq.emplace(dist[i], i);
+	seg_tree seg;
+	seg.build();
+	while (pq.size()) {
+		ll d = pq.top().f, u = pq.top().s;
+		pq.pop();
+		if (d > dist[u]) continue;
+		vector<int> vc;
+		seg.remove(vc, u);
+		for (int v : vc) {
+			if (dist[v+N] > d) {
+				dist[v+N] = d;
+				if (dist[T[v].c] > d+T[v].p)
+					dist[T[v].c] = d+T[v].p,
+					pq.emplace(dist[T[v].c], T[v].c);
+			}
+		}
+	}
+}
+
+int main() {
+	cin.tie(0)->sync_with_stdio(0);
+	cin >> N >> K;
+	for (int i = 0; i < K; ++i) {
+		cin >> T[i].c >> T[i].p >> T[i].a >> T[i].b;
+		--T[i].c, --T[i].a, --T[i].b;
+	}
+	sort(T, T+K, [](auto & a, auto & b) { return a.a < b.a; });
+	vector<ll> L(N+K, 1e18), R(N+K, 1e18), D(N+K);
+	L[0] = R[N-1] = 0;
+	dijkstra(L), dijkstra(R);
+	for (int i = 0; i < N+K; ++i) D[i] = L[i]+R[i];
+	dijkstra(D);
+	for (int i = 0; i < N; ++i)
+		cout << (D[i] < 1e18 ? D[i] : -1) << '\n';
+}
+