verify/aoj_other/aoj_2748.test.cpp

View this file on GitHub
Last update: 2023-05-31 02:53:46+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2748

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2748"
#define ERROR 0.00001

#include "icpc/template.hpp"
#include "icpc/scc.hpp"

void solve(int N) {
    vector<vector<int>> G(N);
    vector<double> p(N);
    REP(i, N) {
        cin >> p[i];
        int m;
        cin >> m;
        REP(j, m) {
            int a;
            cin >> a;
            a--;
            G[i].push_back(a);
        }
    }
    auto sccvec = scc(G);
    vector<int> seen(N);
    double ans = 1;
    for (auto& vec : sccvec) {
        if (seen[vec[0]]) continue;
        double cur = 1;
        queue<int> que;
        for (auto& vi : vec) {
            if (seen[vi]) continue;
            cur *= p[vi];
            que.push(vi);
            seen[vi] = 1;
        }
        ans *= 1 - cur;
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (auto& e : G[v]) {
                if (seen[e]) continue;
                seen[e] = 1;
                que.push(e);
            }
        }
    }
    cout << fixed << setprecision(15) << ans << '\n';
}

int main() {
    int N;
    while (cin >> N, !(N == 0)) solve(N);
    return 0;
}

#line 1 "verify/aoj_other/aoj_2748.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2748"
#define ERROR 0.00001

#line 2 "icpc/template.hpp"

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

using ll = long long;
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;
template <class T> ostream& operator<<(ostream& os, const V<T>& v) {
    os << "[ ";
    for (auto& vi : v) os << vi << ", ";
    return os << "]";
}

#ifdef LOCAL
#define show(x) cerr << __LINE__ << " : " << #x << " = " << x << endl;
#else
#define show(x) true
#endif

using uint = unsigned int;
using ull = unsigned long long;

// g++ -g -fsanitize=undefined,address -DLOCAL -std=gnu++17
#line 2 "icpc/scc.hpp"

#line 4 "icpc/scc.hpp"

// https://onlinejudge.u-aizu.ac.jp/problems/2748

V<V<int>> scc(V<V<int>>& g) {
    int n = int(g.size());
    int now_ord = 0, group_num = 0;
    V<int> vis, low(n), ord(n, -1), ids(n);
    vis.reserve(n);
    auto dfs = [&](auto f, int c) -> void {
        low[c] = ord[c] = now_ord++;
        vis.push_back(c);
        for (auto& e : g[c]) {
            if (ord[e] == -1) {
                f(f, e);
                low[c] = min(low[c], low[e]);
            } else {
                low[c] = min(low[c], ord[e]);
            }
        }
        if (low[c] == ord[c]) {
            while (true) {
                int u = vis.back();
                vis.pop_back();
                ord[u] = n;
                ids[u] = group_num;
                if (u == c) break;
            }
            group_num++;
        }
    };
    REP(i, n) if (ord[i] == -1) dfs(dfs, i);
    V<V<int>> res(group_num);
    REP(i, n) res[group_num - 1 - ids[i]].push_back(i);
    return res;
}
#line 6 "verify/aoj_other/aoj_2748.test.cpp"

void solve(int N) {
    vector<vector<int>> G(N);
    vector<double> p(N);
    REP(i, N) {
        cin >> p[i];
        int m;
        cin >> m;
        REP(j, m) {
            int a;
            cin >> a;
            a--;
            G[i].push_back(a);
        }
    }
    auto sccvec = scc(G);
    vector<int> seen(N);
    double ans = 1;
    for (auto& vec : sccvec) {
        if (seen[vec[0]]) continue;
        double cur = 1;
        queue<int> que;
        for (auto& vi : vec) {
            if (seen[vi]) continue;
            cur *= p[vi];
            que.push(vi);
            seen[vi] = 1;
        }
        ans *= 1 - cur;
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (auto& e : G[v]) {
                if (seen[e]) continue;
                seen[e] = 1;
                que.push(e);
            }
        }
    }
    cout << fixed << setprecision(15) << ans << '\n';
}

int main() {
    int N;
    while (cin >> N, !(N == 0)) solve(N);
    return 0;
}