結果

問題 No.19 ステージの選択
ユーザー tempura-samatempura-sama
提出日時 2016-04-13 18:17:59
言語 C++11
(gcc 11.4.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,040 bytes
コンパイル時間 405 ms
コンパイル使用メモリ 55,940 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-15 00:57:33
合計ジャッジ時間 1,144 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 1 ms
6,940 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 1 ms
6,940 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstring>
using namespace std;

#define N 100

int n;
struct {
	int level;
	int pre_stage;
	int root;
} stages[N];

int visit[N];

int search(int no, int term)
{
	if ( visit[no] || stages[no].root ) {
		// 訪問済み
		return -1;
	}
	if ( stages[no].pre_stage == no ) {
		// 難易度を下げられるステージは存在しない (自分自身が対象のステージになっている)
		return no;
	}
	if ( no == term ) {
		// 循環の末端
		return no;
	}
	visit[no] = 1;

	// noより前のステージのうち、最小難易度のステージを取得
	int min = search(stages[no].pre_stage, term);
	if ( min < 0 ) {
		return -1;
	}

	// noの難易度と比較し、低い方のステージを返す
	return stages[no].level < stages[min].level ? no : min;
}

int main()
{
	cin >> n;
	for ( int i = 0; i < n; i++ ) {
		cin >> stages[i].level >> stages[i].pre_stage;
		stages[i].level *= 10;
		stages[i].pre_stage--;
	}

	// 難易度が下げられるステージと、下げられないステージとに分けられる。
	// 難易度が下げられるステージでも、循環している場合はどれか一つは難易度が下げられない。
	// その場合は循環するステージのうち、最も難易度が低いものを選択すれば良い。

	// 難易度を下げられないステージを探索
	// is_root[N].rootに、難易度を下げられないステージには1が設定される。
	for ( int i = 0; i < n; i++ ) {
		memset(visit, 0, sizeof(visit));
		if ( !visit[stages[i].pre_stage] ) {
			// rootに、難易度の下げられないステージが返る
			int root = search(stages[i].pre_stage, i);
			if ( root >= 0 ) {
				stages[root].root = 1;
			}
		}
	}

	// あとは、.rootが1のステージの難易度はそのまま、0は難易度半分で集計すれば良い。
	int level = 0;
	for ( auto stage : stages ) {
		level += stage.root ? stage.level : (stage.level / 2);
	}

	cout << (level / 10) << "." << (level % 10) << endl;

	return 0;
}
0