結果

問題 No.3200 Sinking Islands
ユーザー 伟国姚
提出日時 2025-07-11 22:04:47
言語 Java
(openjdk 23)
結果
AC  
実行時間 814 ms / 2,000 ms
コード長 3,396 bytes
コンパイル時間 3,041 ms
コンパイル使用メモリ 80,580 KB
実行使用メモリ 63,440 KB
最終ジャッジ日時 2025-07-11 22:05:11
合計ジャッジ時間 18,963 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.*;
import java.util.StringTokenizer;

public class Main {


    static class DSU {
        DSU(int n) {
            init(n);
        }

        private int[] p, sz;

        void init(int n) {
            p = new int[n];
            sz = new int[n];
            for (int i = 0; i < n; i++) {
                p[i] = i;
                sz[i] = 1;
            }
        }

        //用于连接两个连通分量
        void union(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) return;
            sz[x] += sz[y];
            p[y] = x;
        }

        //用于查询某个元素所在连通分量的根节点
        int find(int x) {
            while (p[x] != x) {
                p[x] = p[p[x]];
                x = p[x];
            }
            return x;
        }

        //查询两个元素是否在同一连通分量中
        boolean same(int x, int y) {
            return find(x) == find(y);
        }

        //返回 x 所在连通分量的元素个数
        int size(int x) {
            return sz[find(x)];
        }
    }

    public static void main(String[] args) {
        int n = sc.nextInt(), m = sc.nextInt();
        int[][] a = new int[m][2];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < 2; j++) {
                a[i][j] = sc.nextInt() - 1;
            }
        }
        int q = sc.nextInt();
        int[] qq = new int[q];
        for (int i = 0; i < q; i++) {
            qq[i] = sc.nextInt() - 1;
        }
        boolean[] destroy = new boolean[m];
        for (int d : qq) destroy[d] = true;
        DSU dsu = new DSU(n);
        long ans = 0;
        long cur = n;
        for (int i = 0; i < m; i++) {
            if (!destroy[i]) {
                dsu.union(a[i][0], a[i][1]);
            }
        }
        for (int i = 0; i < n; i++) {
            if (dsu.find(i) == i) {
                int sz = dsu.size(i);
                cur -= sz;
                ans += cur * sz;
            }
        }
        long[] res = new long[q];
        for (int i = q - 1; i >= 0; i--) {
            res[i] = ans;
            int u = a[qq[i]][0], v = a[qq[i]][1];
            if (dsu.same(u, v)) continue;
            int sz1 = dsu.size(u), sz2 = dsu.size(v);
            ans -= (long) sz1 * sz2;
            dsu.union(u, v);
        }
        for (int i = 0; i < q; i++) {
            out.println(res[i]);
        }


        out.close();
    }

    static Kattio sc = new Kattio();
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    static class Kattio {
        static BufferedReader r;
        static StringTokenizer st;

        public Kattio() {
            r = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            try {
                while (st == null || !st.hasMoreTokens()) {
                    st = new StringTokenizer(r.readLine());
                }
                return st.nextToken();
            } catch (Exception e) {
                return null;
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}
0