#77986 (C++11) No.19 ステージの選択

• 問題: No.19 ステージの選択
• ユーザー: togari_takamoto
• 提出日時: 2016-02-25 21:28:28
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 2 ms / 5,000 ms
• コード長: 1,569 bytes
• コンパイル時間: 1,356 ms
• コンパイル使用メモリ: 174,364 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-02 12:30:30
• 合計ジャッジ時間: 2,053 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	1 ms; 5,376 KB
testcase_13	AC	1 ms; 5,376 KB
testcase_14	AC	1 ms; 5,376 KB
testcase_15	AC	1 ms; 5,376 KB
testcase_16	AC	1 ms; 5,376 KB
testcase_17	AC	1 ms; 5,376 KB
testcase_18	AC	1 ms; 5,376 KB
testcase_19	AC	1 ms; 5,376 KB
testcase_20	AC	1 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB
testcase_22	AC	1 ms; 5,376 KB
testcase_23	AC	1 ms; 5,376 KB

ソースコード

#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(1);
	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]) {
			sum2 += 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;
}