結果
| 問題 | No.416 旅行会社 |
| コンテスト | |
| ユーザー |
 Kilisame
|
| 提出日時 | 2016-09-12 15:06:24 |
| 言語 | Java (openjdk 23) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 7,454 bytes |
| コンパイル時間 | 3,861 ms |
| コンパイル使用メモリ | 78,008 KB |
| 最終ジャッジ日時 | 2024-11-14 19:49:35 |
| 合計ジャッジ時間 | 5,721 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
Main.java:38: warning: [removal] Integer(int) in Integer has been deprecated and marked for removal
unreachedBridgeList[islandA].remove(new Integer(islandB));
^
Main.java:39: warning: [removal] Integer(int) in Integer has been deprecated and marked for removal
unreachedBridgeList[islandB].remove(new Integer(islandA));
^
Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error
2 warnings
ソースコード
package puzzle.yukicoder.travelagency;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
public class TravelAgency {
/* 橋が壊れていく過程を考えるのではなく、壊れきった状態をスタート状態とし、そこから巻き戻して1つずつ橋が修復されていったときに、到達できる島がどのように増えていくかを考える。 */
/* 橋の情報は島A、島Bともに10の5乗数までなので、AとBの島のIDを0-99999としたとき、A*10の5乗+BというLong値で管理する */
public static void main(String[] args) {
FastScanner cin = new FastScanner(System.in);
int n = Integer.parseInt(cin.next());
int m = Integer.parseInt(cin.next());
int q = Integer.parseInt(cin.next());
List<Integer>[] unreachedBridgeList = new List[n];
for (int i = 0; i < m; i++) {
int islandA = cin.nextInt() - 1;
int islandB = cin.nextInt() - 1;
if (unreachedBridgeList[islandA] == null) {
unreachedBridgeList[islandA] = new ArrayList<Integer>();
}
unreachedBridgeList[islandA].add(islandB);
if (unreachedBridgeList[islandB] == null) {
unreachedBridgeList[islandB] = new ArrayList<Integer>();
}
unreachedBridgeList[islandB].add(islandA);
}
List<Long> brokenBridgeList = new ArrayList<Long>(q);
for (int i = 0; i < q; i++) {
int islandA = cin.nextInt() - 1;
int islandB = cin.nextInt() - 1;
long brokenBridge = (long) islandA * 100000L + (long) islandB;
brokenBridgeList.add(brokenBridge);
/* 壊れる橋はいったん橋リストから削除する */
unreachedBridgeList[islandA].remove(new Integer(islandB));
unreachedBridgeList[islandB].remove(new Integer(islandA));
}
/* 島のステータス管理。島のIDに対し、何回目に壊れた橋を復旧したらその島に初めて到達できるようになるかを求める */
int[] reached = new int[n];
/* 島1を到達したIDに指定し、eventIndexを-1として実行 */
reachedIsland(0, -1, unreachedBridgeList, reached);
/* 最後に壊れた橋から順に復旧をはじめる */
for (int i = brokenBridgeList.size(); i > 0; i--) {
long recoveredBridge = brokenBridgeList.get(i - 1);
/* その橋が復旧したことで新たに行ける島が増える=片方の島はすでに到達できており、もう片方の島が未到達だった */
int islandA = (int) (recoveredBridge / 100000L);
int islandB = (int) (recoveredBridge % 100000L);
if (reached[islandA] != 0 && reached[islandB] == 0) {
reachedIsland(islandB, i, unreachedBridgeList, reached);
} else if (reached[islandB] != 0 && reached[islandA] == 0) {
reachedIsland(islandA, i, unreachedBridgeList, reached);
} else if (reached[islandA] == 0 && reached[islandB] == 0) {
/* まだ未踏破同士の島をつなぐ橋だった場合、未踏破橋リストに加える */
if (unreachedBridgeList[islandA] == null) {
unreachedBridgeList[islandA] = new ArrayList<Integer>();
}
unreachedBridgeList[islandA].add(islandB);
if (unreachedBridgeList[islandB] == null) {
unreachedBridgeList[islandB] = new ArrayList<Integer>();
}
unreachedBridgeList[islandB].add(islandA);
}
/* それ以外のケース=すでに到達済み同士をつなぐ橋なので、無視 */
}
exit(reached);
}
private static void reachedIsland(int islandId, int eventIndex, List<Integer>[] unreachedBridgeList, int[] reached) {
/* 到達した島に、何回目に壊れた橋を復旧して辿り着いたか記録 */
reached[islandId] = eventIndex;
/* 橋リストから、その島とつながっていてものをピックアップし、つながった先の島IDを確保しつつ橋リストから削除 */
List<Integer> reachedIslandList = unreachedBridgeList[islandId];
for (int reachedIslandId : reachedIslandList) {
if (reached[reachedIslandId] == 0) {
reachedIsland(reachedIslandId, eventIndex, unreachedBridgeList, reached);
}
}
}
private static void exit(int[] reached) {
for (int i = 1; i < reached.length; i++) {
System.out.println(reached[i]);
}
}
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
public FastScanner(InputStream in) {
this.in = in;
}
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
} else {
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte())
return buffer[ptr++];
else
return -1;
}
private static boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
public boolean hasNext() {
while (hasNextByte() && !isPrintableChar(buffer[ptr]))
ptr++;
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() {
long nl = nextLong();
if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
throw new NumberFormatException();
return (int) nl;
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
}