結果

問題 No.416 旅行会社
コンテスト
ユーザー yun_app
提出日時 2016-09-28 18:54:09
言語 Java
(openjdk 23)
結果
MLE  
実行時間 -
コード長 4,718 bytes
コンパイル時間 2,479 ms
コンパイル使用メモリ 79,832 KB
実行使用メモリ 1,506,612 KB
最終ジャッジ日時 2024-11-21 08:20:31
合計ジャッジ時間 100,744 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 RE * 1 TLE * 3 MLE * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
    
    
    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] lines = br.readLine().toString().split(" ");
        int N = Integer.parseInt(lines[0]);
        int M = Integer.parseInt(lines[1]);
        int Q = Integer.parseInt(lines[2]);
        
        for(int i=0;i<M;i++){
            lines = br.readLine().toString().split(" ");
            new Bridge(Integer.parseInt(lines[0]),Integer.parseInt(lines[1]));
        }
        
        search(1);
        HashMap<Integer,Integer> ansMap = new HashMap<Integer,Integer>();
        for(int i=2;i<=N;i++){
            if(pathmap.get(i)==null){
                ansMap.put(i,0);
            }else{
                ansMap.put(i,-1);
            }
        }
        for(int i=0;i<Q;i++){
            String line = br.readLine().toString();
            Bridge.broke(line);
            
            
            for(int j:ansMap.keySet()){
                if(ansMap.get(j) >= 0){
                    continue;
                }
                if(pathmap.get(j)==null){
                    pathmap = new HashMap<Integer,HashMap<Bridge,Boolean>>();
                    search(1);
                }else{
                    for(Bridge keys:pathmap.get(j).keySet()){
                        if(keys.flg == false){
                            pathmap = new HashMap<Integer,HashMap<Bridge,Boolean>>();
                            search(1);
                            break;
                        }
                    }
                }
                int ans = ansMap.get(j)==null?-1:ansMap.get(j);
                if(ans == -1){
                    HashMap<Bridge,Boolean> map = pathmap.get(j);
                    if(map==null){
                        ansMap.put(j,i+1);
                    }
                }
            }
        }
        
//        System.out.println(pathmap.get(2).keySet().size());
        for(int ss:ansMap.keySet()){
            System.out.println(ansMap.get(ss));
        }
    }
    
    //島にたどり着くための橋リスト
    static HashMap<Integer,HashMap<Bridge,Boolean>> pathmap = new HashMap<Integer,HashMap<Bridge,Boolean>>();
    static void search(int start){
        Deque<Integer> deq = new ArrayDeque<Integer>();
        deq.addFirst(start);
        while(!deq.isEmpty()){
            int s = deq.removeFirst();
            if(Bridge.bridgeList.get(s) != null){
                for(Bridge next:Bridge.bridgeList.get(s)){
                    if(next.flg==false){
                        continue;
                    }
                    int g = (s==next.from)?next.to:next.from;
                    HashMap<Bridge,Boolean> brg = pathmap.get(g);
                    if(brg == null){
                        HashMap<Bridge,Boolean> n_brg = hashClone(pathmap.get(s));
                        n_brg.put(next,true);
                        pathmap.put(g,n_brg);
                        deq.addFirst(g);
                    }
                }
            }
        }
        
    }
    
    static HashMap<Bridge,Boolean> hashClone(HashMap<Bridge,Boolean> src){
        HashMap<Bridge,Boolean> ret = new HashMap<Bridge,Boolean>();
        if(src==null){
            return ret;
        }
        for(Bridge key:src.keySet()){
            ret.put(key,src.get(key));
        }
        return ret;
    }
    
    static class Bridge{
        static HashMap<Integer,ArrayList<Bridge>> bridgeList = new HashMap<Integer,ArrayList<Bridge>>();
        static HashMap<String,Bridge> bridgeMap = new HashMap<String,Bridge>();
        int from;
        int to;
        String str;
        boolean flg;
        public Bridge(int f,int t){
            this.from = f;
            this.to   = t;
            this.str  = new StringBuilder().append(f).append(" ").append(t).toString();
            ArrayList<Bridge> arr = bridgeList.get(f);
            if(arr == null){
                arr = new ArrayList<Bridge>();
                bridgeList.put(f,arr);
            }
            arr.add(this);
            
            this.flg = true;
            arr = bridgeList.get(t);
            if(arr == null){
                arr = new ArrayList<Bridge>();
                bridgeList.put(t,arr);
            }
            arr.add(this);
            bridgeMap.put(str,this);
        }
        public static void broke(String st){
            bridgeMap.get(st).flg = false;
        }
    }
    
}
0