結果

問題 No.19 ステージの選択
ユーザー uafr_csuafr_cs
提出日時 2017-11-11 03:31:52
言語 Java21
(openjdk 21)
結果
AC  
実行時間 157 ms / 5,000 ms
コード長 4,152 bytes
コンパイル時間 2,479 ms
コンパイル使用メモリ 81,916 KB
実行使用メモリ 42,980 KB
最終ジャッジ日時 2024-06-02 13:03:49
合計ジャッジ時間 6,242 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 132 ms
42,112 KB
testcase_01 AC 120 ms
42,580 KB
testcase_02 AC 142 ms
42,616 KB
testcase_03 AC 128 ms
42,600 KB
testcase_04 AC 149 ms
42,732 KB
testcase_05 AC 143 ms
42,768 KB
testcase_06 AC 142 ms
42,700 KB
testcase_07 AC 155 ms
42,876 KB
testcase_08 AC 147 ms
42,620 KB
testcase_09 AC 157 ms
42,768 KB
testcase_10 AC 136 ms
42,672 KB
testcase_11 AC 132 ms
42,432 KB
testcase_12 AC 132 ms
42,060 KB
testcase_13 AC 132 ms
42,452 KB
testcase_14 AC 149 ms
42,472 KB
testcase_15 AC 135 ms
42,532 KB
testcase_16 AC 143 ms
42,652 KB
testcase_17 AC 138 ms
42,572 KB
testcase_18 AC 147 ms
42,544 KB
testcase_19 AC 141 ms
42,444 KB
testcase_20 AC 139 ms
42,440 KB
testcase_21 AC 154 ms
42,700 KB
testcase_22 AC 146 ms
42,748 KB
testcase_23 AC 142 ms
42,980 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	
	public static final int FIXED = 10;
	
	// O(N ^ 2)
	public static long calc_DAG(int start, final int N, long[] difficulty, int[] requires, boolean[] visited){
		if(visited[start]){ return 0; }
		
		LinkedList<Integer> queue = new LinkedList<Integer>();
		visited[start] = true;
		queue.add(start);
		
		long ret = 0;
		
		boolean first = true;
		while(!queue.isEmpty()){
			final int curr = queue.poll();
			
			if(first){
				ret += difficulty[curr];
				first = false;
			}else{
				ret += difficulty[curr] / 2;
			}
			
			for(int next = 0; next < N; next++){
				if(requires[next] != curr){ continue; }
				if(visited[next]){ continue; }
				
				visited[next] = true;
				queue.add(next);
			}
		}
		
		return ret;
	}
	
	public static long INF = Long.MAX_VALUE / 2 - 1;
	public static long find_loop_min(int curr, final int N, long[] difficulty, int[] requires, boolean[] visited){
		visited[curr] = true;
		long ret = INF;
		
		//System.out.println(curr + " " + difficulty[curr]);
		for(int next = 0; next < N; next++){
			if(requires[next] != curr){ continue; }
			
			if(visited[next]){
				ret = Math.min(ret, difficulty[curr]);
			}else{
				final long r = find_loop_min(next, N, difficulty, requires, visited);
				if(r < INF){
					ret = Math.min(ret, Math.min(r, difficulty[curr]));
				}else{
					ret = Math.min(ret, r);
				}
			}
		}
		visited[curr] = false;
		//System.out.println(curr + " " + difficulty[curr] + " " + ret);
		
		return ret;
	}
	
	public static long calc_loop(int start, final int N, long[] difficulty, int[] requires, boolean[] visited){
		if(visited[start]){ return 0; }
		
		LinkedList<Integer> queue = new LinkedList<Integer>();
		visited[start] = true;
		queue.add(start);
		
		long ret = 0;
		
		while(!queue.isEmpty()){
			final int curr = queue.poll();
			ret += difficulty[curr] / 2;
			
			for(int next = 0; next < N; next++){
				if(requires[next] != curr){ continue; }
				if(visited[next]){ continue; }
				
				visited[next] = true;
				queue.add(next);
			}
		}
		
		return ret;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		final int N = sc.nextInt();
		long[] difficulty = new long[N];
		int[] requires = new int[N];
		
		int[] ins = new int[N];
		int[] ous = new int[N];
		
		for(int to = 0; to < N; to++){
			difficulty[to] = sc.nextLong() * FIXED;
			
			final int from = sc.nextInt() - 1;
			requires[to] = from;
			if(to == from){ continue; }
			
			ins[to]++; ous[from]++;
		}
		
		long score = 0;
		boolean[] visited = new boolean[N];
		
		// 入次数 = 出次数 = 0 (自己ループを消した場合) があったら優先的にクリアする
		for(int stage = 0; stage < N; stage++){
			if(ins[stage] == 0 && ous[stage] == 0 && !visited[stage]){
				visited[stage] = true;
				score += difficulty[stage];
			}
		}
		// 入次数 = 0 かつ 出次数 >= 1 なら DAG のスタート地点
		for(int stage = 0; stage < N; stage++){
			if(ins[stage] == 0 && ous[stage] >= 1 && !visited[stage]){
				score += calc_DAG(stage, N, difficulty, requires, visited);
			}
		}
		// 以上を処理したあと、ループを処理する
		// ループのある候補は 入時数 = 出自数 = 1 なのでしらみつぶしに探索
		// グラフの形 (入次数が高々1) から、ある頂点から可達なループは多くても一つだけだと言える
		for(int stage = 0; stage < N; stage++){
			if(ins[stage] >= 1 && ous[stage] >= 1 && !visited[stage]){
				final long min = find_loop_min(stage, N, difficulty, requires, visited);
				if(min >= INF){ continue; }
				
				// ループがあったら、そのループから可達なノードをすべて埋める(1/2で)
				final long loop_score = calc_loop(stage, N, difficulty, requires, visited);
				//System.out.println(stage + " " + max + " " + loop_score);
				
				score += (min / 2) + loop_score;
			}
		}
		for(int stage = 0; stage < N; stage++){
			if(!visited[stage]){ score += difficulty[stage]; }
		}
		
		System.out.println((score / FIXED) + "." + (score % FIXED));
	}
}
0