結果

問題 No.19 ステージの選択
ユーザー furon
提出日時 2023-05-31 12:45:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 29 ms / 5,000 ms
コード長 2,837 bytes
コンパイル時間 1,697 ms
コンパイル使用メモリ 143,096 KB
最終ジャッジ日時 2025-02-13 17:05:32
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <string>
#include <queue>
#include <map>
#include <bitset>
#include <set>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <random>

using namespace std;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vd = vector<double>;
using vs = vector<string>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vpdd = vector<pdd>;
const int inf = (1 << 30) - 1;
const ll INF = 1LL << 60;
//const int MOD = 1000000007;
const int MOD = 998244353;

struct SCC {
	using Edge = int;
	using SGraph = vector<vector<Edge>>;

	// input
	SGraph G, rG;

	// result
	vector<vector<int>> scc;
	vector<int> cmp;
	SGraph dag;

	// constructor
	SCC(int N) : G(N), rG(N) {}

	// add edge
	void addedge(int u, int v) {
		G[u].push_back(v);
		rG[v].push_back(u);
	}

	// decomp
	vector<bool> seen;
	vector<int> vs, rvs;
	void dfs(int v) {
		seen[v] = true;
		for (auto e : G[v]) if (!seen[e]) dfs(e);
		vs.push_back(v);
	}
	void rdfs(int v, int k) {
		seen[v] = true;
		cmp[v] = k;
		for (auto e : rG[v]) if (!seen[e]) rdfs(e, k);
		rvs.push_back(v);
	}

	// reconstruct
	set<pair<int, int>> newEdges;
	void reconstruct() {
		int N = (int)G.size();
		int dV = (int)scc.size();
		dag.assign(dV, vector<Edge>());
		newEdges.clear();
		for (int i = 0; i < N; ++i) {
			int u = cmp[i];
			for (auto e : G[i]) {
				int v = cmp[e];
				if (u == v) continue;
				if (!newEdges.count({ u, v })) {
					dag[u].push_back(v);
					newEdges.insert({ u, v });
				}
			}
		}
	}

	// main
	void solve() {
		// first dfs
		int N = (int)G.size();
		seen.assign(N, false);
		vs.clear();
		for (int v = 0; v < N; ++v) if (!seen[v]) dfs(v);

		// back dfs
		int k = 0;
		scc.clear();
		cmp.assign(N, -1);
		seen.assign(N, false);
		for (int i = N - 1; i >= 0; --i) {
			if (!seen[vs[i]]) {
				rvs.clear();
				rdfs(vs[i], k++);
				scc.push_back(rvs);
			}
		}

		reconstruct();
	}
};

int main() {
	int n;
	cin >> n;
	vi l(n), s(n);
	SCC scc(n);
	for (int i = 0; i < n; i++) {
		cin >> l[i] >> s[i];
		s[i]--;
		if(s[i] != i) scc.addedge(s[i], i);
	}
	scc.solve();
	vb visit(n, false);
	
	double ans = 0;
	for (int i = 0; i < scc.scc.size(); i++) {
		if (scc.scc[i].size() == 1) {
			int v = scc.scc[i][0];
			if (visit[s[v]]) ans += l[v] / 2.0;
			else ans += l[v];
			visit[v] = true;
		}
		else {
			double mi = inf;
			for (auto& v : scc.scc[i]) {
				ans += l[v] / 2.0;
				mi = min(mi, l[v] / 2.0);
				visit[v] = true;
			}
			ans += mi;
		}
		
	}
	cout << fixed << setprecision(1);
	cout << ans << endl;

}
0