結果

問題 No.416 旅行会社
ユーザー schwarzahl
提出日時 2017-12-30 23:58:13
言語 Java
(openjdk 23)
結果
AC  
実行時間 2,999 ms / 4,000 ms
コード長 8,260 bytes
コンパイル時間 3,433 ms
コンパイル使用メモリ 94,684 KB
実行使用メモリ 127,804 KB
最終ジャッジ日時 2024-12-14 20:27:47
合計ジャッジ時間 39,153 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package practice;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.Scanner;
import java.util.Set;
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solveC();
    }
    private void solveA() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(N);
    }
    private void solveB() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(N);
    }
    private void solveC() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int Q = sc.nextInt();
        int[] A = new int[M];
        int[] B = new int[M];
        for (int i = 0; i < M; i++) {
            A[i] = sc.nextInt();
            B[i] = sc.nextInt();
        }
        int[] C = new int[Q];
        int[] D = new int[Q];
        Set<Integer> broken = new HashSet<>();
        for (int i = 0; i < Q; i++) {
            C[i] = sc.nextInt();
            D[i] = sc.nextInt();
            broken.add(C[i] * N + D[i]);
        }
        CustomUnionFind uf = new CustomUnionFind(N + 1);
        for (int i = 0; i < M; i++) {
            if (!broken.contains(A[i] * N + B[i])) {
                uf.union(A[i], B[i]);
            }
        }
        int[] ans = new int[N + 1];
        for (int id : uf.getSet(1)) {
            ans[id] = -1;
        }
        for (int i = Q - 1; i >= 0; i--) {
            Set<Integer> set1 = uf.getSet(1);
            boolean set1ContainC = set1.contains(C[i]);
            boolean set1ContainD = set1.contains(D[i]);
            if (set1ContainC && !set1ContainD) {
                for (int id : uf.getSet(D[i])) {
                    ans[id] = i + 1;
                }
            }
            if (!set1ContainC && set1ContainD) {
                for (int id : uf.getSet(C[i])) {
                    ans[id] = i + 1;
                }
            }
            uf.union(C[i], D[i]);
        }
        for (int id = 2; id <= N; id++) {
            System.out.println(ans[id]);
        }
    }
    private void solveD() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(N);
    }
    private void solveE() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(N);
    }
    private void solveF() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(N);
    }
    interface Graph {
        void link(int from, int to, long cost);
        Optional<Long> getCost(int from, int to);
        int getVertexNum();
    }
    interface FlowResolver {
        long maxFlow(int from, int to);
    }
    /**
     * グラフの行列による実装
     * 接点数の大きいグラフで使うとMLEで死にそう
     */
    class ArrayGraph implements Graph {
        private Long[][] costArray;
        private int vertexNum;
        public ArrayGraph(int n) {
            costArray = new Long[n][];
            for (int i = 0; i < n; i++) {
                costArray[i] = new Long[n];
            }
            vertexNum = n;
        }
        @Override
        public void link(int from, int to, long cost) {
            costArray[from][to] = new Long(cost);
        }
        @Override
        public Optional<Long> getCost(int from, int to) {
            return Optional.ofNullable(costArray[from][to]);
        }
        @Override
        public int getVertexNum() {
            return vertexNum;
        }
    }
    /**
     * DFS(深さ優先探索)による実装
     * 計算量はO(E*MaxFlow)のはず (E:辺の数, MaxFlow:最大フロー)
     */
    class DfsFlowResolver implements FlowResolver {
        private Graph graph;
        public DfsFlowResolver(Graph graph) {
            this.graph = graph;
        }
        /**
         * 最大フロー(最小カット)を求める
         * @param from 始点(source)のID
         * @param to 終点(target)のID
         * @return 最大フロー(最小カット)
         */
        public long maxFlow(int from, int to) {
            long sum = 0L;
            long currentFlow;
            do {
                currentFlow = flow(from, to, Long.MAX_VALUE / 3, new boolean[graph.getVertexNum()]);
                sum += currentFlow;
            } while (currentFlow > 0);
            return sum;
        }
        /**
         * フローの実行 グラフの更新も行う
         * @param from 現在いる節点のID
         * @param to 終点(target)のID
         * @param current_flow ここまでの流量
         * @param passed 既に通った節点か否かを格納した配列
         * @return 終点(target)に流した流量/戻りのグラフの流量
         */
        private long flow(int from, int to, long current_flow, boolean[] passed) {
            passed[from] = true;
            if (from == to) {
                return current_flow;
            }
            for (int id = 0; id < graph.getVertexNum(); id++) {
                if (passed[id]) {
                    continue;
                }
                Optional<Long> cost = graph.getCost(from, id);
                if (cost.orElse(0L) > 0) {
                    long nextFlow = current_flow < cost.get() ? current_flow : cost.get();
                    long returnFlow = flow(id, to, nextFlow, passed);
                    if (returnFlow > 0) {
                        graph.link(from, id, cost.get() - returnFlow);
                        graph.link(id, from, graph.getCost(id, from).orElse(0L) + returnFlow);
                        return returnFlow;
                    }
                }
            }
            return 0L;
        }
    }
    /**
     * 1-indexedのBIT配列
     */
    class BinaryIndexedTree {
        private long[] array;
        public BinaryIndexedTree(int size) {
            this.array = new long[size + 1];
        }
        /**
         * 指定した要素に値を加算する
         * 計算量はO(logN)
         * @param index 加算する要素の添字
         * @param value 加算する量
         */
        public void add(int index, long value) {
            for (int i = index; i < array.length; i += (i & -i)) {
                array[i] += value;
            }
        }
        /**
         * 1〜指定した要素までの和を取得する
         * 計算量はO(logN)
         * @param index 和の終端
         * @return 1〜indexまでの和
         */
        public long getSum(int index) {
            long sum = 0L;
            for (int i = index; i > 0; i -= (i & -i)) {
                sum += array[i];
            }
            return sum;
        }
    }
    interface UnionFind {
        void union(int A, int B);
        boolean judge(int A, int B);
    }
    class CustomUnionFind extends ArrayUnionFind {
        Map<Integer, Set<Integer>> map;
        public CustomUnionFind(int size) {
            super(size);
            map = new HashMap<>();
            for (int i = 0; i < size; i++) {
                map.put(i, new HashSet<>());
                map.get(i).add(i);
            }
        }
        @Override
        public void union(int A, int B) {
            int rootA = root(A);
            int rootB = root(B);
            if (rootA != rootB) {
                if (rank[rootA] < rank[rootB]) {
                    parent[rootA] = rootB;
                    map.get(rootB).addAll(map.get(rootA));
                } else {
                    parent[rootB] = rootA;
                    map.get(rootA).addAll(map.get(rootB));
                    if (rank[rootA] == rank[rootB]) {
                        rank[rootA]++;
                    }
                }
            }
        }
        public Set<Integer> getSet(int id) {
            return map.get(root(id));
        }
    }
    /**
     * 配列によるUnionFindの実装
     */
    class ArrayUnionFind implements UnionFind {
        int[] parent;
        int[] rank;
        public ArrayUnionFind(int size) {
            parent = new int[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
            }
            rank = new int[size];
        }
        @Override
        public void union(int A, int B) {
            int rootA = root(A);
            int rootB = root(B);
            if (rootA != rootB) {
                if (rank[rootA] < rank[rootB]) {
                    parent[rootA] = rootB;
                } else {
                    parent[rootB] = rootA;
                    if (rank[rootA] == rank[rootB]) {
                        rank[rootA]++;
                    }
                }
            }
        }
        @Override
        public boolean judge(int A, int B) {
            return root(A) == root(B);
        }
        protected int root(int id) {
            if (parent[id] == id) {
                return id;
            }
            parent[id] = root(parent[id]);
            return parent[id];
        }
    }
    /**
     * 素数のユーティリティ
     */
    class PrimeNumberUtils {
        boolean[] isPrimeArray;
        List<Integer> primes;
        /**
         * 素数判定の上限となる値を指定してユーティリティを初期化
         * @param limit 素数判定の上限(この値以上が素数であるか判定しない)
         */
        public PrimeNumberUtils(int limit) {
            if (limit > 10000000) {
                System.err.println("上限の値が高すぎるため素数ユーティリティの初期化でTLEする可能性が大変高いです");
            }
            primes = new ArrayList<>();
            isPrimeArray = new boolean[limit];
            if (limit > 2) {
                primes.add(2);
                isPrimeArray[2] = true;
            }
            for (int i = 3; i < limit; i += 2) {
                if (isPrime(i, primes)) {
                    primes.add(i);
                    isPrimeArray[i] = true;
                }
            }
        }
        public List<Integer> getPrimeNumberList() {
            return primes;
        }
        public boolean isPrime(int n) {
            return isPrimeArray[n];
        }
        private boolean isPrime(int n, List<Integer> primes) {
            for (int prime : primes) {
                if (n % prime == 0) {
                    return false;
                }
                if (prime > Math.sqrt(n)) {
                    break;
                }
            }
            return true;
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0