Ideone.com

fork download

copy

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
#include<cmath>
#include<bitset>
#include<map>
#define test(t) while(t--)
#define cin(n) scanf("%d",&n)
#define cout(n) printf("%d\n",n)
#define rep(i,a,n) for(i=a;i<=n;i++)
#define vi vector<int>
#define vii vector< vector<int> >
#define vpii vector< pair<int,int> >
#define mii map<int,int>
#define pb push_back
#define mp make_pair
#define imax (int) 1000000007
#define ill long long
#define gc getchar_unlocked
using namespace std;
#define mod 1000000007
int a[105][4];
int n;
 
double recurse(double prob1,int node,int value)
{
    double val[109];
    double ans=double(0);
    for(int i=1;i<=n;i++)
    {
      if(a[i][0]==0)
        val[i]=prob1;
      else if(a[i][0]==1)
      {
        val[i]=1-((1-val[a[i][2]])*(1-val[a[i][1]]));
      }
      else
      {
        val[i]=val[a[i][1]]*val[a[i][2]];
      }
    }
    return val[n];
}
double recurse2(double prob1,int node,int value)
{
    double ans=0.00000000;
    if(a[node][0]==0)
        ans= prob1;
    if(a[node][0]==1)
        ans= 1-(recurse2(prob1,a[node][2],0)*recurse2(prob1,a[node][1],0));
    if(a[node][0]==2)
        ans= (recurse2(prob1,a[node][2],1)*recurse2(prob1,a[node][1],1));
    return ans;
}
 
double binary(double low,double high)
{
    double mid=(low+high)/2,k;
    k=recurse2(mid,n,1);
    if(fabs(k-0.5)<0.0000001)
        return mid;
    else if(k>0.5)
        return binary(low,mid);
    else
        return binary(mid,high);
 
}
int main()
{
    int t,m,i,j,k,l,o;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i][0]);
            if(a[i][0]!=0)
                scanf("%d%d",&a[i][1],&a[i][2]);
        }
        printf("%.5lf\n",binary(0.0,1.0));
 
    }
return 0;
}

I2luY2x1ZGU8Y3N0ZGlvPgojaW5jbHVkZTxpb3N0cmVhbT4KI2luY2x1ZGU8dmVjdG9yPgojaW5jbHVkZTxjc3RyaW5nPgojaW5jbHVkZTxhbGdvcml0aG0+CiNpbmNsdWRlPHNldD4KI2luY2x1ZGU8Y21hdGg+CiNpbmNsdWRlPGJpdHNldD4KI2luY2x1ZGU8bWFwPgojZGVmaW5lIHRlc3QodCkgd2hpbGUodC0tKQojZGVmaW5lIGNpbihuKSBzY2FuZigiJWQiLCZuKQojZGVmaW5lIGNvdXQobikgcHJpbnRmKCIlZFxuIixuKQojZGVmaW5lIHJlcChpLGEsbikgZm9yKGk9YTtpPD1uO2krKykKI2RlZmluZSB2aSB2ZWN0b3I8aW50PgojZGVmaW5lIHZpaSB2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4KI2RlZmluZSB2cGlpIHZlY3RvcjwgcGFpcjxpbnQsaW50PiA+CiNkZWZpbmUgbWlpIG1hcDxpbnQsaW50PgojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIGltYXggKGludCkgMTAwMDAwMDAwNwojZGVmaW5lIGlsbCBsb25nIGxvbmcKI2RlZmluZSBnYyBnZXRjaGFyX3VubG9ja2VkCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbW9kIDEwMDAwMDAwMDcKaW50IGFbMTA1XVs0XTsKaW50IG47Cgpkb3VibGUgcmVjdXJzZShkb3VibGUgcHJvYjEsaW50IG5vZGUsaW50IHZhbHVlKQp7CiAgICBkb3VibGUgdmFsWzEwOV07CiAgICBkb3VibGUgYW5zPWRvdWJsZSgwKTsKICAgIGZvcihpbnQgaT0xO2k8PW47aSsrKQogICAgewogICAgICBpZihhW2ldWzBdPT0wKQogICAgICAgIHZhbFtpXT1wcm9iMTsKICAgICAgZWxzZSBpZihhW2ldWzBdPT0xKQogICAgICB7CiAgICAgICAgdmFsW2ldPTEtKCgxLXZhbFthW2ldWzJdXSkqKDEtdmFsW2FbaV1bMV1dKSk7CiAgICAgIH0KICAgICAgZWxzZQogICAgICB7CiAgICAgICAgdmFsW2ldPXZhbFthW2ldWzFdXSp2YWxbYVtpXVsyXV07CiAgICAgIH0KICAgIH0KICAgIHJldHVybiB2YWxbbl07Cn0KZG91YmxlIHJlY3Vyc2UyKGRvdWJsZSBwcm9iMSxpbnQgbm9kZSxpbnQgdmFsdWUpCnsKICAgIGRvdWJsZSBhbnM9MC4wMDAwMDAwMDsKICAgIGlmKGFbbm9kZV1bMF09PTApCiAgICAgICAgYW5zPSBwcm9iMTsKICAgIGlmKGFbbm9kZV1bMF09PTEpCiAgICAgICAgYW5zPSAxLShyZWN1cnNlMihwcm9iMSxhW25vZGVdWzJdLDApKnJlY3Vyc2UyKHByb2IxLGFbbm9kZV1bMV0sMCkpOwogICAgaWYoYVtub2RlXVswXT09MikKICAgICAgICBhbnM9IChyZWN1cnNlMihwcm9iMSxhW25vZGVdWzJdLDEpKnJlY3Vyc2UyKHByb2IxLGFbbm9kZV1bMV0sMSkpOwogICAgcmV0dXJuIGFuczsKfQoKZG91YmxlIGJpbmFyeShkb3VibGUgbG93LGRvdWJsZSBoaWdoKQp7CiAgICBkb3VibGUgbWlkPShsb3craGlnaCkvMixrOwogICAgaz1yZWN1cnNlMihtaWQsbiwxKTsKICAgIGlmKGZhYnMoay0wLjUpPDAuMDAwMDAwMSkKICAgICAgICByZXR1cm4gbWlkOwogICAgZWxzZSBpZihrPjAuNSkKICAgICAgICByZXR1cm4gYmluYXJ5KGxvdyxtaWQpOwogICAgZWxzZQogICAgICAgIHJldHVybiBiaW5hcnkobWlkLGhpZ2gpOwoKfQppbnQgbWFpbigpCnsKICAgIGludCB0LG0saSxqLGssbCxvOwogICAgc2NhbmYoIiVkIiwmdCk7CiAgICB3aGlsZSh0LS0pCiAgICB7CiAgICAgICAgc2NhbmYoIiVkIiwmbik7CiAgICAgICAgZm9yKGk9MTtpPD1uO2krKykKICAgICAgICB7CiAgICAgICAgICAgIHNjYW5mKCIlZCIsJmFbaV1bMF0pOwogICAgICAgICAgICBpZihhW2ldWzBdIT0wKQogICAgICAgICAgICAgICAgc2NhbmYoIiVkJWQiLCZhW2ldWzFdLCZhW2ldWzJdKTsKICAgICAgICB9CiAgICAgICAgcHJpbnRmKCIlLjVsZlxuIixiaW5hcnkoMC4wLDEuMCkpOwoKICAgIH0KcmV0dXJuIDA7Cn0K

Runtime error #stdin #stdout 0s 2732KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/nxo2cn

language:

C++ 4.3.2 (gcc-4.3.2)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language