結果

問題 No.19 ステージの選択
ユーザー togari_takamototogari_takamoto
提出日時 2016-02-25 21:19:58
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,570 bytes
コンパイル時間 1,617 ms
コンパイル使用メモリ 174,504 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-22 13:46:46
合計ジャッジ時間 2,464 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
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 <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi  = vector<int>; using vb  = vector<bool>; using vd  = vector<double>; using vl  = vector<ll>;
using vvi = vector<vi>;  using vvb = vector<vb>;   using vvd = vector<vd>;     using vvl = vector<vl>;

#define REP(i,n) for(ll i=0; i<(n); ++i)
#define FOR(i,b,n) for(ll i=(b); i<(n); ++i)
#define ALL(v) (v).begin(), (v).end()

using Graph = vvi;
vvi scc(Graph & g, Graph & rg) {
	ll n = g.size();
	vb used(n, false);
	function<void(int, vi&)> dfs = [&](int v, vi & order) {
		if (used[v]) return;
		used[v] = true;
		for (auto &e : g[v]) dfs(e, order);
		order.push_back(v);
	};
	
	vi order;
	{
		REP(i, n) dfs(i, order);
		reverse(ALL(order));
	}

	vvi cmp;
	{
		g.swap(rg);
		used = vb(n, false);
		REP(i, n) if (!used[order[i]]) {
			cmp.push_back(vi());
			dfs(order[i], cmp.back());
		}
		g.swap(rg);
	}

	return cmp;
}

Graph create_rg(const Graph & g) {
	Graph rg(g.size());
	REP(from, g.size()) for (auto& to : g[from]) rg[to].push_back(from);
	return rg;
}

int main() {
	cout << fixed << setprecision(5);
	ll n; cin >> n;
	vl l(n); vl s(n);
	REP(i,n) cin >> l[i] >> s[i];

	Graph g(n);
	REP(i, n) g[s[i]-1].push_back(i);
	auto rg = create_rg(g);

	auto v = scc(g, rg);

	ll sum1 = 0, sum2 = 0;
	REP(i, v.size()) {
		if (v[i].size() == 1 && s[v[i][0]] - 1 != v[i][0]) {
			sum1 += l[v[i][0]];
		} else {
			vi lv; for (auto j : v[i]) lv.push_back(l[j]);
			sort(ALL(lv));
			
			sum1 += lv[0];
			FOR(j, 1, lv.size()) sum2 += lv[j];
		}
	}
	cout << sum1 + sum2 / 2.0 << endl;
	return 0;
}
0