結果

問題 No.19 ステージの選択
ユーザー togari_takamoto
提出日時 2016-02-25 21:28:28
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,569 bytes
コンパイル時間 2,079 ms
コンパイル使用メモリ 173,928 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-23 10:04:31
合計ジャッジ時間 2,616 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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(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;
}
0