結果
問題 | No.416 旅行会社 |
ユーザー | Kilisame |
提出日時 | 2016-09-12 14:34:04 |
言語 | Java21 (openjdk 21) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,547 bytes |
コンパイル時間 | 3,758 ms |
コンパイル使用メモリ | 78,940 KB |
実行使用メモリ | 108,908 KB |
最終ジャッジ日時 | 2024-11-17 03:55:30 |
合計ジャッジ時間 | 73,983 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | AC | 131 ms
46,176 KB |
testcase_02 | AC | 131 ms
101,472 KB |
testcase_03 | AC | 133 ms
46,360 KB |
testcase_04 | AC | 137 ms
101,428 KB |
testcase_05 | AC | 145 ms
46,396 KB |
testcase_06 | AC | 166 ms
101,544 KB |
testcase_07 | AC | 226 ms
48,152 KB |
testcase_08 | AC | 441 ms
108,908 KB |
testcase_09 | AC | 1,352 ms
60,332 KB |
testcase_10 | TLE | - |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | TLE | - |
testcase_19 | TLE | - |
testcase_20 | TLE | - |
ソースコード
package puzzle.yukicoder.travelagency; import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.Scanner; public class TravelAgency { /* 橋が壊れていく過程を考えるのではなく、壊れきった状態をスタート状態とし、そこから巻き戻して1つずつ橋が修復されていったときに、到達できる島がどのように増えていくかを考える。 */ /* 橋の情報は島A、島Bともに10の5乗数までなので、AとBの島のIDを0-99999としたとき、A*10の5乗+BというLong値で管理する */ public static void main(String[] args) { Scanner cin = new Scanner(System.in); int n = Integer.parseInt(cin.next()); int m = Integer.parseInt(cin.next()); int q = Integer.parseInt(cin.next()); List<Long> unreachedBridgeList = new ArrayList<Long>(m); for (int i = 0; i < m; i++) { long bridge = (Long.parseLong(cin.next()) - 1L) * 100000L + (Long.parseLong(cin.next()) - 1L); unreachedBridgeList.add(bridge); } List<Long> brokenBridgeList = new ArrayList<Long>(q); for (int i = 0; i < q; i++) { long brokenBridge = (Long.parseLong(cin.next()) - 1L) * 100000L + (Long.parseLong(cin.next()) - 1L); brokenBridgeList.add(brokenBridge); /* 壊れる橋はいったん橋リストから削除する */ unreachedBridgeList.remove(brokenBridge); } cin.close(); /* 島のステータス管理。島の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) { /* まだ未踏破同士の島をつなぐ橋だった場合、未踏破橋リストに加える */ unreachedBridgeList.add(recoveredBridge); } /* それ以外のケース=すでに到達済み同士をつなぐ橋なので、無視 */ } exit(reached); } private static void reachedIsland(int islandId, int eventIndex, List<Long> unreachedBridgeList, int[] reached) { /* 到達した島に、何回目に壊れた橋を復旧して辿り着いたか記録 */ reached[islandId] = eventIndex; /* 橋リストから、その島とつながっていてものをピックアップし、つながった先の島IDを確保しつつ橋リストから削除 */ List<Integer> reachedIslandList = new ArrayList<Integer>(); Iterator<Long> bridgeIterator = unreachedBridgeList.iterator(); while (bridgeIterator.hasNext()) { long bridge = bridgeIterator.next(); int islandA = (int) (bridge / 100000L); int islandB = (int) (bridge % 100000L); if (islandA == islandId && reached[islandB] == 0 && !reachedIslandList.contains(islandB)) { reachedIslandList.add(islandB); bridgeIterator.remove(); } else if (islandB == islandId && reached[islandA] == 0 && !reachedIslandList.contains(islandA)) { reachedIslandList.add(islandA); bridgeIterator.remove(); } } for (int reachedIslandId : reachedIslandList) { reachedIsland(reachedIslandId, eventIndex, unreachedBridgeList, reached); } } private static void exit(int[] reached) { for (int i = 1; i < reached.length; i++) { System.out.println(reached[i]); } } }