結果

問題 No.19 ステージの選択
ユーザー uafr_cs
提出日時 2017-11-11 02:12:11
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 4,028 bytes
コンパイル時間 2,131 ms
コンパイル使用メモリ 84,280 KB
実行使用メモリ 55,096 KB
最終ジャッジ日時 2024-11-24 16:35:05
合計ジャッジ時間 6,399 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18 WA * 6
権限があれば一括ダウンロードができます

ソースコード

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;
			// 
			if(to == from){ continue; }
			
			requires[to] = from;
			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