Comments
0

Sorry, I forgot.
This is the original explanation table.

L, R Selection Explanation
L = 1, R = 1 Delete edge 1. This is not a “beautiful” deletion because there exists a path from vertex 2 to vertex 6 with a total weight of 15, which is greater than K = 12.
L = 1, R = 2 Delete edges 1 and 2. This is not a “beautiful” deletion because there exists a path from vertex 2 to vertex 6 with a total weight of 15, which is greater than K = 12.
L = 1, R = 3 Delete edges 1, 2, and 3. This is a “beautiful” deletion because the heaviest path is from vertex 3 to vertex 6 with a weight of 9, which does not exceed K = 12.
L = 1, R = 4 Delete edges 1, 2, 3, and 4. This is a “beautiful” deletion because the heaviest path is from vertex 3 to vertex 6 with a weight of 9, which does not exceed K = 12.
L = 1, R = 5 Delete edges 1, 2, 3, 4, and 5. This is a “beautiful” deletion because there are no remaining paths between any pair of vertices.
L = 2, R = 2 Delete edge 2. This is not a “beautiful” deletion because there exists a path from vertex 5 to vertex 6 with a total weight of 19, which is greater than K = 12.
L = 2, R = 3 Delete edges 2 and 3. This is a “beautiful” deletion because the heaviest path is from vertex 3 to vertex 6 with a weight of 9, which does not exceed K = 12.
L = 2, R = 4 Delete edges 2, 3, and 4. This is a “beautiful” deletion because the heaviest path is from vertex 3 to vertex 6 with a weight of 9, which does not exceed K = 12.
L = 2, R = 5 Delete edges 2, 3, 4, and 5. This is a “beautiful” deletion because the heaviest path is from vertex 1 to vertex 2 with a weight of 3, which does not exceed K = 12.
L = 3, R = 3 Delete edge 3. This is a “beautiful” deletion because the heaviest path is from vertex 3 to vertex 6 with a weight of 9, which does not exceed K = 12.
L = 3, R = 4 Delete edges 3 and 4. This is a “beautiful” deletion because the heaviest path is from vertex 3 to vertex 6 with a weight of 9, which does not exceed K = 12.
L = 3, R = 5 Delete edges 3, 4, and 5. This is a “beautiful” deletion because the heaviest path is from vertex 2 to vertex 4 with a weight of 9, which does not exceed K = 12.
L = 4, R = 4 Delete edge 4. This is not a “beautiful” deletion because there exists a path from vertex 4 to vertex 6 with a total weight of 23, which is greater than K = 12.
L = 4, R = 5 Delete edges 4 and 5. This is not a “beautiful” deletion because there exists a path from vertex 3 to vertex 4 with a total weight of 14, which is greater than K = 12.
L = 5, R = 5 Delete edge 5. This is not a “beautiful” deletion because there exists a path from vertex 3 to vertex 4 with a total weight of 14, which is greater than K = 12.
0

Auto comment: topic has been updated by bao987 (previous revision, new revision, compare).
On bao987 → Counting SCCs ?, 9 months ago
0

Is it true that they really share the same trick? Thank you.
On bao987 → Counting SCCs ?, 9 months ago
0

Problem 2. WiFi Stations (7 points)

Alice is designing a wired internet connection system for WiFi stations. Specifically, on the coordinate plane there are n WiFi stations, numbered from 1 to n. The i-th station (1 ≤ i ≤ n) has coordinates (xi, yi).

In order for a station to broadcast internet, Alice must connect it to the internet via a cable to one station. If station i already has internet, it can broadcast within a radius of ri, and any station within that radius will also have internet. That station can in turn continue to broadcast within its own radius, and so on…

More precisely, if a station with coordinates (x, y) and radius r has internet, then any station with coordinates (u, v) such that (x – u)² + (y – v)² ≤ r² will also have internet.

Alice wants to connect cables to as few stations as possible so that all n stations can broadcast internet.

Requirement: Given the coordinates and radii of the stations, help Alice determine the minimum number of stations that need to be connected via cables so that all n stations can broadcast internet.

Input: (from the file WIFI.INP)

The first line contains a positive integer n (n ≤ 2 × 10^5), the number of stations.

Each of the next n lines contains three integers xi, yi, ri (|xi|, |yi| ≤ 10^6; 0 < ri ≤ 10^6). Note: There may be multiple stations at the same location.

Output: (to the file WIFI.OUT)

Output a single positive integer — the minimum number of stations that need to be connected via cables so that all n stations can broadcast internet.

Constraints:

Subtask 1 (20%): n ≤ 10

Subtask 2 (20%): n ≤ 1000

Subtask 3 (20%): All stations’ coordinates lie on the same straight line

Subtask 4 (20%): ri ≤ 10

Subtask 5 (20%): No additional constraints

This is the full problem statement that I’m asking about. Perhaps the problem you suggested to me and this one are two completely different problems.
On bao987 → Counting SCCs ?, 9 months ago
0

Yes, exactly. So I need some ideas from everyone — maybe a sweep line?
On bao987 → Counting SCCs ?, 9 months ago
0

Oh, sorry, I completely forgot to mention what I need. Right now, I don’t know how to solve this problem yet. I’m guessing it might be related to geometry or sweepline, but I don’t have a concrete approach. I’d like everyone’s help — do you have any ideas for a solution?
On bao987 → Counting SCCs ?, 9 months ago
0

Auto comment: topic has been updated by bao987 (previous revision, new revision, compare).
0

Maybe I went a bit overkill and couldn’t come up with anything simpler, so I ended up implementing something quite similar to the Min25 sieve combined with Lagrange interpolation. Anyway, thank you very much! P.S.: I'm still a bit unsure whether one particular problem truly requires using the Min25 sieve or not.
0

Oh oh, thank you — even though it’ll probably get me “judged” :))))
0

You mean using a segmented sieve combined with the trick of storing precomputed values in constant arrays, like the number of elements with exponent , etc., and then computing the answer?
0

Thank you, I guess I have to learn the Min25 sieve now, because when I manually ran the segmented sieve with n, m = 3e7, it already took about 1–2 seconds, so it can’t be optimized further.
0

Sorry, but since m ≤ 3e8, creating an array for storage is completely impossible.
I've also implemented this algorithm considering it as a specific solution for n, m ≤ 2e6.
0

Thank you
0

Thank you, but libraries like GNU PBDS are probably not allowed on OJ. If using a BBST, could you give me some suggestions? For example, how to insert, delete, and query?
0

Ah, I understand how sweepline works now, but the problem is my code is running into TLE. So, is it really necessary to switch to a BBST? If not, how can I optimize it now (since I haven't learned BBST yet)? Link code: https://ide.usaco.guide/OVaceGEffjT2SpKEf-5
0

Sorry, may I ask a bit more: do you mean that each event corresponds to a vertex sweep? And if we sweep by vertices, then each vertex will have two edges associated with it in one event. So how do we handle each of these events?

Apologies — I'm still not very good at these kinds of problems.
0

Auto comment: topic has been updated by bao987 (previous revision, new revision, compare).