結果
問題 | No.19 ステージの選択 |
ユーザー |
![]() |
提出日時 | 2016-06-12 22:36:17 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 4,050 bytes |
コンパイル時間 | 1,906 ms |
コンパイル使用メモリ | 174,596 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-23 10:05:17 |
合計ジャッジ時間 | 2,858 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
/*_ooOoo_o8888888o88" . "88(| -_- |)O\ = /O____/`---'\____.' \\| |// `./ \\||| : |||// \/ _||||| -:- |||||- \| | \\\ - /// | || \_| ''\---/'' | |\ .-\__ `-` ___/-. /___`. .' /--.--\ `. . __."" '< `.___\_<|>_/___.' >'"".| | : `- \`.;`\ _ /`;.`/ - ` : | |\ \ `-. \_ __\ /__ _/ .-` / /======`-.____`-.___\_____/___.-`____.-'======`=---='^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^pass System Test!*/#include <bits/stdc++.h>using namespace std;template <typename T>std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {if (!v.empty()) {out << '[';std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));out << "\b\b]";}return out;}template <typename T1, typename T2>std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &p) {out << "[" << p.first << ", " << p.second << "]";return out;}template <class T, class U>void chmin(T &t, U f) {if (t > f) t = f;}template <class T, class U>void chmax(T &t, U f) {if (t < f) t = f;}template <typename T>void uniq(vector<T> &v) {v.erase(unique(v.begin(), v.end()), v.end());}class StronglyConnectedComponents {private:StronglyConnectedComponents() {}int N;std::vector<int> cmp;std::vector<std::vector<int>> super_graph;size_t componentsSize;void dfs(int v, std::vector<bool> &used, std::vector<int> &vs,const std::vector<std::vector<int>> &g) {used[v] = true;for (int w : g[v])if (!used[w]) dfs(w, used, vs, g);vs.push_back(v);}void rdfs(int v, int k, std::vector<bool> &used,const std::vector<std::vector<int>> &rg) {used[v] = true;cmp[v] = k;for (int w : rg[v])if (!used[w]) rdfs(w, k, used, rg);}public:StronglyConnectedComponents(const std::vector<std::vector<int>> &g) {N = g.size();cmp.resize(N);std::vector<std::vector<int>> rg(N);for (int i = 0; i < N; ++i)for (int v : g[i]) rg[v].push_back(i);std::vector<bool> used(N, false);std::vector<int> vs;for (int i = 0; i < N; ++i)if (!used[i]) dfs(i, used, vs, g);used.assign(N, false);componentsSize = 0;for (int i = vs.size() - 1; i >= 0; i--)if (!used[vs[i]]) rdfs(vs[i], componentsSize++, used, rg);super_graph.resize(componentsSize);for (int i = 0; i < N; ++i) {std::vector<bool> vis(componentsSize, false);for (int v : g[i]) {if (vis[cmp[v]] || cmp[v] == cmp[i]) continue;super_graph[cmp[i]].push_back(cmp[v]);vis[cmp[v]] = true;}}}std::vector<int> getComponentIDs() { return cmp; }std::vector<std::vector<int>> getComponentList() {std::vector<std::vector<int>> clist(componentsSize);for (int i = 0; i < N; ++i) clist[cmp[i]].push_back(i);return clist;}std::vector<std::vector<int>> getSuperGraph() { return super_graph; }int size() { return componentsSize; }};int main() {cin.tie(0);ios::sync_with_stdio(false);int N;cin >> N;vector<vector<int>> g(N);vector<int> level(N);for (int i = 0; i < N; ++i) {int S;cin >> level[i] >> S;S--;g[S].push_back(i);}StronglyConnectedComponents scc(g);vector<vector<int>> sg = scc.getSuperGraph();vector<vector<int>> rsg(sg.size());for (int i = 0; i < sg.size(); ++i)for (int v : sg[i]) {rsg[v].push_back(i);}vector<vector<int>> clist = scc.getComponentList();double ans = 0.0;for (int i = 0; i < clist.size(); ++i) {int sum = 0;int mi = 1e9;for (int c : clist[i]) {sum += level[c];mi = min(mi, level[c]);}if (rsg[i].size() == 0) {sum -= mi;ans += mi;}ans += (sum / 2.0);}printf("%.1f\n", ans);}