結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a) for (int i = 0; i < (a); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); i++)
#define repr(i, a) for (int i = (a) - 1; i >= 0; i--)
#define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--)
template<class T1, class T2> bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
typedef long long ll;

class SCC {
public:
	vector<vector<int>> G, rG, H, cc;
	vector<int> cid;
	SCC(int n) : G(n), rG(n), vis(n), cid(n, -1) {}
	void add(int u, int v) {
		G[u].push_back(v);
		rG[v].push_back(u);
	}
	void build() {
		rep(i, G.size()) if (!vis[i]) {
			dfs(i);
		}
		int k = 0;
		repr(i, order.size()) if (cid[order[i]] == -1) {
			dfs2(order[i], k++);
		}
		cc.resize(k);
		rep(i, G.size()) cc[cid[i]].push_back(i);
		set<pair<int, int>> es;
		rep(i, G.size()) for (int next : G[i]) {
			if (cid[i] != cid[next]) {
				es.emplace(cid[i], cid[next]);
			}
		}
		H.resize(k);
		for (auto e : es) {
			H[e.first].push_back(e.second);
		}
	}
	int size() { return H.size(); }
	vector<int> &operator[](int k) { return H[k]; }
private:
	vector<bool> vis;
	vector<int> order;
	void dfs(int curr) {
		vis[curr] = true;
		for (int next : G[curr]) if (!vis[next]) {
			dfs(next);
		}
		order.push_back(curr);
	}
	void dfs2(int curr, int k) {
		cid[curr] = k;
		for (int next : rG[curr]) if (cid[next] == -1) {
			dfs2(next, k);
		}
	}
};

int main() {
	int n;
	cin >> n;
	vector<int> l(n), s(n);
	SCC scc(n);
	rep(i, n) {
		cin >> l[i] >> s[i];
		scc.add(s[i] - 1, i);
	}
	scc.build();

	vector<double> mn(scc.size(), 1e9);
	vector<double> sum(scc.size());
	rep(i, scc.size()) {
		rep(j, scc.cc[i].size()) {
			chmin(mn[i], l[scc.cc[i][j]]);
			sum[i] += l[scc.cc[i][j]];
		}
	}

	double ans = 0;
	vector<char> vis(scc.size(), false);
	rep(i, scc.size()) if (!vis[i]) {
		queue<int> q;
		q.push(i);
		while (!q.empty()) {
			int curr = q.front(); q.pop();
			ans += sum[curr] / 2;
			if (!vis[curr]) ans += mn[curr] / 2;
			for (int next : scc[curr]) {
				vis[next] = true;
				q.push(next);
			}
		}
	}

	printf("%.1f\n", ans);

	return 0;
}
0