結果

問題 No.19 ステージの選択
ユーザー furonfuron
提出日時 2023-05-31 12:45:17
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 2,837 bytes
コンパイル時間 2,055 ms
コンパイル使用メモリ 147,824 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-08 21:01:41
合計ジャッジ時間 3,096 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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