結果

問題 No.19 ステージの選択
ユーザー uafr_csuafr_cs
提出日時 2017-11-11 03:26:00
言語 Java21
(openjdk 21)
結果
AC  
実行時間 189 ms / 5,000 ms
コード長 4,021 bytes
コンパイル時間 2,232 ms
コンパイル使用メモリ 77,788 KB
実行使用メモリ 57,352 KB
最終ジャッジ日時 2023-08-24 23:33:35
合計ジャッジ時間 7,238 ms
ジャッジサーバーID
(参考情報)
judge12 / judge11
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 151 ms
56,808 KB
testcase_01 AC 151 ms
56,812 KB
testcase_02 AC 153 ms
56,632 KB
testcase_03 AC 156 ms
56,820 KB
testcase_04 AC 169 ms
56,800 KB
testcase_05 AC 167 ms
57,036 KB
testcase_06 AC 165 ms
57,080 KB
testcase_07 AC 165 ms
57,352 KB
testcase_08 AC 165 ms
57,248 KB
testcase_09 AC 166 ms
56,964 KB
testcase_10 AC 155 ms
56,740 KB
testcase_11 AC 145 ms
56,556 KB
testcase_12 AC 147 ms
56,984 KB
testcase_13 AC 149 ms
56,752 KB
testcase_14 AC 159 ms
56,656 KB
testcase_15 AC 162 ms
57,140 KB
testcase_16 AC 164 ms
56,712 KB
testcase_17 AC 161 ms
57,244 KB
testcase_18 AC 189 ms
57,064 KB
testcase_19 AC 169 ms
56,780 KB
testcase_20 AC 155 ms
56,532 KB
testcase_21 AC 162 ms
57,088 KB
testcase_22 AC 158 ms
56,844 KB
testcase_23 AC 160 ms
56,944 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 なのでしらみつぶしに探索
		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