Home » 国际竞赛 » Details

USACO 2022 January Contest, Gold Problem 2. Farm Updates

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

USACO 2022 January Contest, Gold Problem 2. Farm Updates

Farmer John operates a collection of $N$ farms ( $1 \leq N \leq 10^{5}$ ), conveniently numbered $1 \dots N$ . Initially, there are no roads connecting these farms to each-other, and each farm is actively producing milk.

Due to the dynamic nature of the economy, Farmer John needs to make changes to his farms according to a series of $Q$ update operations ( $0 \leq Q \leq 2 \cdot 10^{5}$ ). Update operations come in three possible forms:

(D x) Deactivate an active farm $x$ , so it no longer produces milk.
(A x y) Add a road between two active farms $x$ and $y$ .
(R e) Remove the $e$ th road that was previously added ( $e = 1$ is the first road that was added).

A farm $x$ that is actively producing milk, or that can reach another active farm via a series of roads, is called a "relevant" farm. For each farm $x$ , please calculate the maximum $i$ ( $0 \leq i \leq Q$ ) such that $x$ is relevant after the $i$ -th update.

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

The first line of input contains $N$ and $Q$ . The next $Q$ lines each contain an update of one of the following forms:

D x
A x y
R e

It is guaranteed that for updates of type R, $e$ is at most the number of roads that have been added so far, and no two updates of type R have the same value of $e$ .

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

Please output $N$ lines, each containing an integer in the range $0 \dots Q$ .

SAMPLE INPUT:

SAMPLE OUTPUT:

In this example, roads are removed in the order $(2, 3), (1, 2), (2, 4)$ .

Farm $1$ is relevant just before $(1, 2)$ is removed.
Farm $2$ is relevant just before $(2, 4)$ is removed.
Farm $3$ is relevant just before $(2, 3)$ is removed.
Farms $4$ and $5$ are still active after all queries. Therefore they both stay relevant, and the output for both should be $Q$ .

SCORING:

Tests 2 through 5 satisfy $N \leq 10^{3}$ , $Q \leq 2 \cdot 10^{3}$
Test cases 6 through 20 satisfy no additional constraints.

Problem credits: Benjamin Qi

USACO 2022 January Contest, Gold Problem 2. Farm Updates 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

The idea is to process the updates in reverse order and maintain which farms are relevant. Note that once a farm becomes relevant, it never becomes irrelevant due to the assumption that roads are only added between active farms.

For updates of type R, add the $e$ -th edge to the graph. If exactly one endpoint of this edge was previously relevant, mark all vertices in the connected component of the other endpoint as relevant as well.

For updates of type D, if vertex $x$ was not previously relevant, then mark every vertex in its connected component as relevant.

For updates of type A, do nothing.

We can process these operations in $O (N + Q)$ time.

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class GarbageCollection {
    static List<Integer>[] adj = null;
    static int[] answers;

    // marks everything in the connected component of a 
    // as relevant
    static void dfs(int a, int time) {
        if (answers[a] == 0) {
            answers[a] = time;
            for (int b : adj[a]) {
                dfs(b, time);
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int q = Integer.parseInt(tokenizer.nextToken());
        adj = new List[n + 1];
        for (int a = 1; a <= n; a++) {
            adj[a] = new ArrayList<>();
        }
        answers = new int[n + 1];
        List<Edge> added = new ArrayList<>();
        Edge[] removed = new Edge[q];
        int[] deactivated = new int[q];
        Set<Integer> alwaysActive = new HashSet<>();
        for (int a = 1; a <= n; a++) {
            alwaysActive.add(a);
        }
        for (int j = 0; j < q; j++) {
            tokenizer = new StringTokenizer(in.readLine());
            char type = tokenizer.nextToken().charAt(0);
            if (type == 'D') {
                int a = Integer.parseInt(tokenizer.nextToken());
                deactivated[j] = a;
                alwaysActive.remove(a);
            } else if (type == 'A') {
                int a = Integer.parseInt(tokenizer.nextToken());
                int b = Integer.parseInt(tokenizer.nextToken());
                added.add(new Edge(a, b));
            } else {
                int k = Integer.parseInt(tokenizer.nextToken());
                removed[j] = added.get(k - 1);
                added.set(k - 1, null);
            }
        }
        for (Edge edge : added) {
            if (edge != null) {
                adj[edge.from].add(edge.to);
                adj[edge.to].add(edge.from);
            }
        }
        for (int a : alwaysActive) {
            dfs(a, q);
        }
        for (int j = q - 1; j > 0; j--) {
            if (deactivated[j] != 0) {
                dfs(deactivated[j], j);
            } else if (removed[j] != null) {
                int a = removed[j].from;
                int b = removed[j].to;
                adj[a].add(b);
                adj[b].add(a);
                if (answers[a] != 0 || answers[b] != 0) {
                    dfs(a, j);
                    dfs(b, j);
                }
            }
        }
        StringBuilder out = new StringBuilder();
        for (int a = 1; a <= n; a++) {
            out.append(answers[a]).append('\n');
        }
        System.out.print(out);
    }
 
    static class Edge {
        final int from;
        final int to;
 
        Edge(int from, int to) {
            this.from = from;
            this.to = to;
        }
    }
}

[/hide]