結果

問題 No.529 帰省ラッシュ
コンテスト
ユーザー spielatoon
提出日時 2019-07-10 15:57:58
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 2,944 bytes
コンパイル時間 2,546 ms
コンパイル使用メモリ 112,472 KB
実行使用メモリ 75,556 KB
最終ジャッジ日時 2024-10-15 15:29:28
合計ジャッジ時間 9,263 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 TLE * 1 -- * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Linq;
using System.Text;
using System.Collections.Generic;

public class Hello{
    
    private static int distination;
    private static int[] answer;
    private static Town[] towns;
    private static Road[] roads;
    private static int pleyNum;
    
    public static void Main(){
        var line = System.Console.ReadLine().Split(' ');
        int N = int.Parse(line[0]);
        int M = int.Parse(line[1]);
        int Q = int.Parse(line[2]);
        towns = new Town[N];
        for(int i=0;i<N;i++){
            towns[i] = new Town();
        }
        roads = new Road[M];
        for(int i=0;i<M;i++){
            line = System.Console.ReadLine().Split(' ');
            roads[i] = new Road();
            roads[i].A = int.Parse(line[0])-1;
            roads[i].B = int.Parse(line[1])-1;
            towns[roads[i].A].neighborhood.Add(i);
            towns[roads[i].B].neighborhood.Add(i);
        }
        answer = new int[2]{-2,-2};
        pleyNum = 0;
        for(int i=0;i<Q;i++){
            line = System.Console.ReadLine().Split(' ');
            if(line[0]=="1"){
                //獲物出現
                towns[int.Parse(line[1])-1].pley.Add(int.Parse(line[2]));
                pleyNum++;
            }else if(pleyNum==0){
                System.Console.WriteLine(-1);
            }else{
                //熊帰省
                distination = int.Parse(line[2])-1;
                GoHome(int.Parse(line[1])-1,new List<int>(),-1,-1);
                if(answer[1]>=0){
                    towns[answer[1]].pley.Remove(answer[0]);
                    pleyNum--;
                }
                System.Console.WriteLine(answer[0]);
                answer = new int[2]{-2,-2};
            }
        }
    }
    private static void GoHome(int now, List<int> usedRoad, int max, int maxTown){
        //現在地の獲物を捕らえる
        if(towns[now].pley.Count>0){
            int tmp = towns[now].pley.Max();
            if(max<tmp){
                max = tmp;
                maxTown = now;
            }
        }
        var canMove = towns[now].neighborhood.Except(usedRoad).ToList();
        if(now==distination){
            //ここまでで捕らえた最大の獲物を記録する
            if(answer[0]<max){
                answer[0] = max;
                answer[1] = maxTown;
            }
        }
        if(canMove.Count>0){
            //移動可能な街へ移動する
            foreach(int road in canMove){
                var newUsed = new List<int>(usedRoad);
                newUsed.Add(road);
                int next = (roads[road].A==now ? roads[road].B : roads[road].A);
                GoHome(next,newUsed,max,maxTown);
            }
        }
        return;
    }
}
public class Road{
    public int A;
    public int B;
}
public class Town{
    public List<int> pley = new List<int>();
    public List<int> neighborhood = new List<int>();
}
0