Home » 国际竞赛 » Details

USACO 2021 December Contest, Platinum Problem 1. Tickets

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午12:23

USACO 2021 December Contest, Platinum Problem 1. Tickets

Bessie is going on a hiking excursion! The trail that she is currently traversing consists of $N$ checkpoints labeled $1 \dots N$ ( $1 \leq N \leq 10^{5}$ ).

There are $K$ ( $1 \leq K \leq 10^{5}$ ) tickets available for purchase. The $i$ -th ticket can be purchased at checkpoint $c_{i}$ ( $1 \leq c_{i} \leq N$ ) for price $p_{i}$ ( $1 \leq p_{i} \leq 10^{9}$ ) and provides access to all of checkpoints $[a_{i}, b_{i}]$ ( $1 \leq a_{i} \leq b_{i} \leq N$ ). Before entering any checkpoint, Bessie must have purchased a ticket that allows access to that checkpoint. Once Bessie has access to a checkpoint, she may return to it at any point in the future. She may travel between two checkpoints to which she has access, regardless of whether their labels differ by 1 or not.

For each of $i \in [1, N]$ , output the minimum total price required to purchase access to both checkpoints $1$ and $N$ if Bessie initially has access to only checkpoint $i$ . If it is impossible to do so, print $- 1$ instead.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $N$ and $K$ .Each of the next $K$ lines contains four integers $c_{i}$ , $p_{i}$ , $a_{i}$ , and $b_{i}$ for each $1 \leq i \leq K$ .

OUTPUT FORMAT (print output to the terminal / stdout):

$N$ lines, one for each checkpoint.

SAMPLE INPUT:

7 6
4 1 2 3
4 10 5 6
2 100 7 7
6 1000 1 1
5 10000 1 4
6 100000 5 6

SAMPLE OUTPUT:

If Bessie starts at checkpoint $i = 4$ , then one way for Bessie to purchase access to checkpoints $1$ and $N$ is as follows:

Purchase the first ticket at checkpoint $4$ , giving Bessie access to checkpoints $2$ and $3$ .
Purchase the third ticket at checkpoint $2$ , giving Bessie access to checkpoint $7$ .
Return to checkpoint $4$ and purchase the second ticket, giving Bessie access to checkpoints $5$ and $6$ .
Purchase the fourth ticket at checkpoint $6$ , giving Bessie access to checkpoint $1$ .

SCORING:

Test cases 1-7 satisfy $N, K \leq 1000$ .
Test cases 8-19 satisfy no additional constraints.

Problem credits: Benjamin Qi

USACO 2021 December Contest, Platinum Problem 1. Tickets 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Timothy Qian)

Consider each ticket and each checkpoint as a node in a graph. We draw the following edges: An edge from checkpoint $i$ of weight $p_{j}$ to ticket $j$ if $i = c_{j}$ , an edge from ticket $i$ to checkpoint $j$ of weight $0$ if $a_{i} \leq j \leq b_{i}$ . Each time we go to ticket $j$ , it can be seen as activating an edge to ticket $j$ for a price $p_{j}$ . Then the goal is for each $i$ to pay the minimum to activate some edges such that starting from checkpoint $i$ , we can visit checkpoint $1$ and checkpoint $N$ .

Now consider the optimal set of edges that we pick. Say we start at checkpoint $s$ . The edges we picked must form a path from $s$ to $1$ and $s$ to $N$ . Consider the nodes we visit in the path from checkpoint $s$ to checkpoint $1$ in that order and call this list $L$ , and similarly for the nodes we visited on the path from $s$ to checkpoint $N$ and call this $R$ . Consider indices $i, j$ such that $L [i] = R [j]$ , but for any $x > i, y > j$ , we have $L [x] \neq R [y]$ . This can be viewed as the "last common node" of $L, R$ . This exists as long as $L, R$ have at least one node in common, which they do, namely checkpoint $s$ . Note that $i, j$ need not be unique, but this does not matter. Let $z = L [i] = R [j]$ . Then the rest of list $L$ after index $i$ consists of a path from $z$ to $1$ . Similarly, the rest of list $R$ consists of a path from $z$ to $N$ . The first part of list $L$ consists of a path from $s$ to $z$ , and similarly for the first part of list $R$ . Note that the paths from $z$ to $1$ and $z$ to $N$ do not contain any tickets in common. So for every optimal set of edges that we pick, we can decompose that edges into three parts: a path from our starting checkpoint to a node $z$ , and two disjoint paths from $z$ to checkpoint $1$ and to checkpoint $N$ .

We first compute the shortest paths from any node to checkpoint $1$ . The same can be analogously done for computing the shortest paths from any node to checkpoint $N$ . We instead reverse the edges, and compute the minimum distance from checkpoint $1$ to any other node. The main idea is we use a multi-source Dijkstra's algorithm on a Segment Tree. We first initialize checkpoint $1$ at a distance of $0$ , and every other node at a distance of infinity. We put all checkpoints in a minimum priority queue based on their distance. After popping the top checkpoint, let it be $i$ , we must find all tickets that have not yet been visited yet that contain $i$ . To do this, we put the tickets in a Segment Tree based on their index after sorting the tickets by $a_{j}$ , their left interval value. Then in each node of the Segment Tree, we store the maximum $b_{j}$ , or the right interval value, of all tickets in the contained interval. Now we can descend down the Segment Tree to remove all the intervals that contain $c_{i}$ . When we remove an interval from the Segment Tree, we can set its right coordinate to $- 1$ . Note that we don't actually need to add this ticket to the priority queue. This is because this ticket's distance must be the same as the distance to the checkpoint that is currently being processed. Thus, we can just process these removed tickets immediately. Overall, these Segment Tree operations will take $O (N \log N)$ time, because each interval gets removed exactly once. Running this Dijkstra's algorithm thus takes $O (N \log N)$ time.

Finally, let $D_{L} [i], D_{R} [i]$ be the distances for going to checkpoint $1$ and a ticket with checkpoint $N$ starting from node $i$ as computed above. Then we initialize each node $i$ at a distance of $D_{L} [i] + D_{R} [i]$ . Then we once again run the same Dijkstra's algorithm as above to compute the distance to each node. The final distances to each checkpoint stores the desired answers.

Benjamin + Timothy Qian's Code:

#include <bits/stdc++.h>
 
using namespace std;
 
struct Ticket {
	int c, p, a, b;
};
 
struct SegmentTree {
	int n, sz;
	vector<int> mx;
	vector<Ticket> tickets;
 
	SegmentTree(vector<Ticket> tickets) : tickets(tickets) {
		n = 1;
		sz = (int)tickets.size();
		while (n < sz) {
			n <<= 1;
		}
		mx.assign(2 * n, 0);
		for (int i = 0; i < n; ++i) {
			if (i < sz) {
				mx[i + n] = tickets[i].b;
			} else {
				mx[i + n] = -1;				
			}
		}
		for (int i = n - 1; i >= 1; --i) {
			pull(i);
		}
	}
 
	void pull(int i) {
		mx[i] = max(mx[2 * i], mx[2 * i + 1]);
	}
 
	void remove(vector<int>& v, int p, int i = 1, int l = 0, int r = -1) {
		if (r == -1) {
			r += n;
		}
		if (l >= sz || tickets[l].a > p || mx[i] < p) {
			return;
		} else if (l == r) {
			mx[i] = -1;
			v.push_back(l);
		} else {
			int m = (l + r) >> 1;
			remove(v, p, 2 * i, l, m);
			remove(v, p, 2 * i + 1, m + 1, r);
			pull(i);
		}
	}
};	
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	const long long INF = 1e18;
	int n, k;
	cin >> n >> k;
	vector<Ticket> tickets(k);
	for (auto& t : tickets) {
		cin >> t.c >> t.p >> t.a >> t.b;
		--t.c, --t.a, --t.b;
	}
	sort(tickets.begin(), tickets.end(), [](const auto& l, const auto& r) {
		return l.a < r.a;
	});
	auto dijkstra = [&](vector<long long> dist) {
		priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
		for (int i = n; i < n + k; ++i) {
			dist[tickets[i - n].c] = min(dist[tickets[i - n].c], dist[i] + tickets[i - n].p);
		}
		for (int i = 0; i < n; ++i) {
			if (dist[i] < INF) {
				pq.push({dist[i], i});
			}
		}
		SegmentTree seg(tickets);
		while (!pq.empty()) {
			auto x = pq.top();
			pq.pop();
			if (x.first > dist[x.second]) {
				continue;
			}
			vector<int> removed;
			seg.remove(removed, x.second);
			for (int r : removed) {
				if (dist[r + n] > x.first) {
					dist[r + n] = x.first;
					if (dist[tickets[r].c] > x.first + tickets[r].p) {
						dist[tickets[r].c] = x.first + tickets[r].p;
						pq.push({dist[tickets[r].c], tickets[r].c});
					}
				}
			}
		}
		return dist;
	};
	vector<long long> start_left(n + k, INF);
	start_left[0] = 0;
	vector<long long> dist_left = dijkstra(start_left);
	vector<long long> start_right(n + k, INF);
	start_right[n - 1] = 0;
	vector<long long> dist_right = dijkstra(start_right);
	vector<long long> dist(n + k);
	for (int i = 0; i < n + k; ++i) {
		dist[i] = dist_left[i] + dist_right[i];
	}
	dist = dijkstra(dist);
	for (int i = 0; i < n; ++i) {
		if (dist[i] < INF) {
			cout << dist[i] << '\n';
		} else {
			cout << -1 << '\n';
		}
	}
}

Author's note: This was created at the same time as (and is vaguely related to) EGOI 2021 Lanterns.
[/hide]