結果

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

ソースコード

diff # 

#include <bits/stdc++.h>

#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif

using namespace std;

#define REP(i, a, b) for(int i = (a); i < int(b); ++i)
#define rep(i, n) REP(i, 0, n)
#define ALL(x) begin(x), end(x)

template<class T> inline void chmax(T &a, const T &b) { if(a < b) a = b; }
template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; }

// SCC Strongly Connected Component 強連結成分分解
struct SCC {
	typedef vector<vector<int>> graph;
	
	int V;
	int cV;
	graph G;
	graph cG;
	vector<int> cmp;
	vector<int> vs;
	vector<bool> used;
	vector<vector<int>> nodes;

	SCC(int V_):V(V_), G(V_), cmp(V_), used(V_) {}
	SCC(const graph &G_):V(G_.size()), G(G_), cmp(V), used(V) {}

	void add_edge(int from, int to) {
		if(from != to) G[from].emplace_back(to);
	}

	void dfs(int v) {
		used[v] = true;
		for(const auto &to : G[v]) {
			if(!used[to]) dfs(to);
		}
		vs.emplace_back(v);
	}

	void rdfs(int v, int k, graph &rG) {
		used[v] = true;
		cmp[v] = k;
		for(const auto &to : rG[v]) {
			if(!used[to]) rdfs(to, k, rG);
		}
	}

	int scc() {
		vs.clear();
		fill(used.begin(), used.end(), false);

		for(int v = 0; v < V; ++v) {
			if(!used[v]) dfs(v);
		}

		graph rG(V);
		for(int v = 0; v < V; ++v) {
			for(const auto &to : G[v]) {
				rG[to].emplace_back(v);
			}
		}

		fill(used.begin(), used.end(), false);
		int k = 0;
		for(int i = static_cast<int>(vs.size()) - 1; i >= 0; --i) {
			if(!used[vs[i]]) rdfs(vs[i], k++, rG);
		}
		return k;
	}

	void construct() {
		cV = scc();
		cG.clear();
		cG.resize(cV);
		nodes.resize(cV);

		for(int v = 0; v < V; ++v) {
			nodes[cmp[v]].emplace_back(v);
			for(const auto &to : G[v]) {
				if(cmp[v] != cmp[to]) cG[cmp[v]].emplace_back(cmp[to]);
			}
		}

		for(auto &es : cG) {
			sort(es.begin(), es.end());
			es.erase(unique(es.begin(), es.end()), es.end());
		}
	}
};

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout.setf(ios::fixed);
	cout.precision(1);

	int n;
	cin >> n;

	SCC scc(n);
	vector<int> difficulty(n);
	
	for(int v = 0; v < n; ++v) {
		int s;
		cin >> difficulty[v] >> s;
		scc.add_edge(s - 1, v);
	}

	scc.construct();
	vector<int> in_degree(scc.cV, 0);
	for(int cv = 0; cv < scc.cV; ++cv) {
		for(const auto &to : scc.cG[cv]) {
			++in_degree[to];
		}
	}

	queue<int> que;
	for(int cv = 0; cv < scc.cV; ++cv) {
		if(in_degree[cv] == 0) que.emplace(cv);
	}

	int ans = 0;
	vector<int> cnt(in_degree);
	while(!que.empty()) {
		const int cv = que.front();
		que.pop();

		int min_difficulty = INT_MAX;
		int sum_difficulty = 0;
		
		for(const auto &v : scc.nodes[cv]) {
			chmin(min_difficulty, difficulty[v]);
			sum_difficulty += difficulty[v];
		}

		ans += sum_difficulty;
		if(in_degree[cv] == 0) ans += min_difficulty;

		for(const auto &to : scc.cG[cv]) {
			if(--cnt[to] == 0) que.emplace(to);
		}
	}

	cout << ans / 2.0 << endl;

	return EXIT_SUCCESS;
}
0