結果

問題 No.19 ステージの選択
ユーザー maine_honzuki
提出日時 2020-05-05 13:09:03
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 2,146 bytes
コンパイル時間 2,731 ms
コンパイル使用メモリ 184,432 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-26 07:36:08
合計ジャッジ時間 3,087 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

struct StronglyConnectedComponent {
public:
    vector<vector<int>> G, R, T;
    //
private:
    vector<int> cmp, ord;
    vector<bool> used;
    //
public:
    StronglyConnectedComponent(int n) : G(n), R(n), cmp(n, -1), used(n, false) {}
    void add_edge(int u, int v) {
        G[u].emplace_back(v);
        R[v].emplace_back(u);
    }
    //
private:
    void dfs(int now) {
        if (used[now])
            return;
        used[now] = true;
        for (auto nxt : G[now])
            dfs(nxt);
        ord.emplace_back(now);
    }
    void rdfs(int now, int count) {
        if (cmp[now] != -1)
            return;
        cmp[now] = count;
        for (auto to : R[now])
            rdfs(to, count);
    }
    //
public:
    int build() {
        int n = (int)G.size();
        for (int i = 0; i < n; i++)
            dfs(i);
        reverse(ord.begin(), ord.end());
        int group = 0;
        for (auto& i : ord) {
            if (cmp[i] == -1) {
                rdfs(i, group);
                group++;
            }
        }
        T.resize(group);
        for (int i = 0; i < n; i++) {
            for (auto& to : G[i]) {
                int s = cmp[i], t = cmp[to];
                if (s != t)
                    T[s].emplace_back(t);
            }
        }
        return group;
    }
    int operator[](int k) { return cmp[k]; }
};
using SCC = StronglyConnectedComponent;

//
int main() {
    int N, L[101], S[101];
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> L[i] >> S[i];
        S[i]--;
    }

    SCC scc(N);
    for (int i = 0; i < N; i++) {
        scc.add_edge(S[i], i);
    }
    scc.build();

    map<int, int> M;
    for (int i = 0; i < N; i++) {
        if (scc[i] == scc[S[i]]) {
            if (M.count(scc[i]))
                M[scc[i]] = min(M[scc[i]], L[i]);
            else
                M[scc[i]] = L[i];
        }
    }

    double ans = 0;
    for (int i = 0; i < N; i++) {
        ans += L[i] / 2.0;
    }
    for (auto& p : M) {
        ans += p.second / 2.0;
    }
    cout << fixed << setprecision(1);
    cout << ans << endl;
}
0