結果
| 問題 | No.416 旅行会社 |
| ユーザー |
 hiromi_ayase
|
| 提出日時 | 2016-08-27 00:41:11 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 5,328 bytes |
| コンパイル時間 | 3,214 ms |
| コンパイル使用メモリ | 86,872 KB |
| 実行使用メモリ | 82,080 KB |
| 最終ジャッジ日時 | 2024-11-08 17:49:01 |
| 合計ジャッジ時間 | 13,008 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 21 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.util.ArrayList;import java.util.Collections;import java.util.HashSet;import java.util.List;import java.util.NoSuchElementException;import java.util.Set;public class Main {private static final int C = 100000;public static void main(String[] args) {FastScanner sc = new FastScanner();int N = sc.nextInt();int M = sc.nextInt();int Q = sc.nextInt();UnionFind uf = new UnionFind(N);Set<Long> set = new HashSet<>();for (int i = 0; i < M; i++) {long a = sc.nextInt() - 1;long b = sc.nextInt() - 1;set.add(a * C + b);}List<Long> q = new ArrayList<>();for (int i = 0; i < Q; i++) {long a = sc.nextInt() - 1;long b = sc.nextInt() - 1;set.remove(a * C + b);q.add(a * C + b);}int[] ans = new int[N];List<List<Integer>> v = new ArrayList<>();for (int i = 0; i < N; i++) {v.add(new ArrayList<Integer>());}for (long x : set) {int a = (int) (x / C);int b = (int) (x % C);uf.union(a, b);}for (int i = 0; i < N; i++) {int root = uf.find(i);if (uf.find(i) == uf.find(0)) {ans[i] = -1;}v.get(root).add(i);}Collections.reverse(q);int count = 0;for (long x : q) {int a = (int) (x / C);int b = (int) (x % C);int rootA = uf.find(a);int rootB = uf.find(b);if (rootA != rootB) {int root0 = uf.find(0);if (root0 == rootA) {int root = rootB;for (int y : v.get(root)) {ans[y] = Q - count;}} else if (root0 == rootB) {int root = rootA;for (int y : v.get(root)) {ans[y] = Q - count;}}List<Integer> la = v.get(rootA);List<Integer> lb = v.get(rootB);if (la.size() < lb.size()) {List<Integer> tmp = la;la = lb;lb = tmp;}for (int y : lb) {la.add(y);}uf.union(a, b);v.set(uf.find(a), la);}count++;}StringBuilder sb = new StringBuilder();for (int i = 1; i < N; i++) {sb.append(ans[i]);sb.append("\n");}System.out.println(sb);}}class UnionFind {private int[] table;private int[] rank;public UnionFind(int size) {this.table = new int[size];this.rank = new int[size];for (int i = 0; i < size; i++) {this.table[i] = i;this.rank[i] = 1;}}public boolean isSame(int node1, int node2) {return find(node1) == find(node2);}public int find(int node) {if (table[node] == node) {return node;} else {return table[node] = find(table[node]);}}public void union(int node1, int node2) {int root1 = find(node1);int root2 = find(node2);if (rank[root1] < rank[root2]) {table[root1] = root2;} else if (rank[root1] > rank[root2]) {table[root2] = root1;} else if (root1 != root2) {table[root2] = root1;rank[root1]++;}}}class FastScanner {public static String debug = null;private final InputStream in = System.in;private int ptr = 0;private int buflen = 0;private byte[] buffer = new byte[1024];private boolean eos = false;private boolean hasNextByte() {if (ptr < buflen) {return true;} else {ptr = 0;try {if (debug != null) {buflen = debug.length();buffer = debug.getBytes();debug = "";eos = true;} else {buflen = in.read(buffer);}} catch (IOException e) {e.printStackTrace();}if (buflen < 0) {eos = true;return false;} else if (buflen == 0) {return false;}}return true;}private int readByte() {if (hasNextByte())return buffer[ptr++];elsereturn -1;}private static boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}private void skipUnprintable() {while (hasNextByte() && !isPrintableChar(buffer[ptr]))ptr++;}public boolean isEOS() {return this.eos;}public boolean hasNext() {skipUnprintable();return hasNextByte();}public String next() {if (!hasNext())throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while (isPrintableChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}public long nextLong() {if (!hasNext())throw new NoSuchElementException();long n = 0;boolean minus = false;int b = readByte();if (b == '-') {minus = true;b = readByte();}if (b < '0' || '9' < b) {throw new NumberFormatException();}while (true) {if ('0' <= b && b <= '9') {n *= 10;n += b - '0';} else if (b == -1 || !isPrintableChar(b)) {return minus ? -n : n;} else {throw new NumberFormatException();}b = readByte();}}public int nextInt() {return (int) nextLong();}public long[] nextLongList(int n) {return nextLongTable(1, n)[0];}public int[] nextIntList(int n) {return nextIntTable(1, n)[0];}public long[][] nextLongTable(int n, int m) {long[][] ret = new long[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {ret[i][j] = nextLong();}}return ret;}public int[][] nextIntTable(int n, int m) {int[][] ret = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {ret[i][j] = nextInt();}}return ret;}}