水題，只要 dfs 過去就秒掉了
// BEGIN CUT HERE
// END CUT HERE
#line 5 "GCAcode.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string\>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;
#ifdef DEBUG
#define VAR(a,b) \_\_typeof(b) a=(b)
#define debug(...) printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)
#else
#define VAR(a,b) \_\_typeof(b) a=(b)
#define debug(...)
#endif
typedef unsigned int uint;
typedef long long int Int;
typedef unsigned long long int UInt;
#define Set(a,s) memset(a,s,sizeof(a))
#define Pln() printf("\\n")
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define M 52
#define PB push\_back
#define oo INT\_MAX
#define FOR(a,b) for(VAR(a,(b).begin());a!=(b).end();++a)
#define eps 1e-9
#define X first
#define Y second
inline bool xdy(double x,double y){return x>y+eps;}
inline bool xddy(double x,double y){return x>y-eps;}
inline bool xcy(double x,double y){return x<y-eps;}
inline bool xcdy(double x,double y){return x<y+eps;}
const Int mod=1000000007;
class ProbabilityTree
{
public:
struct node{
double prob1,prob2;
double rp;
}nodes\[M\];
vector<int\> mz\[M\];
int vis\[M\];
void dfs(int now,int dep){
// printf("%d %d\\n",now,dep);
vis\[now\]=1;
FOR(it,mz\[now\]){
int to=\*it;
nodes\[to\].rp=nodes\[now\].rp\*nodes\[to\].prob1+(1-nodes\[now\].rp)\*nodes\[to\].prob2;
if(!vis\[to\])dfs(to,dep+1);
}
}
vector <int\> getOdds(vector <string\> tree, int lowerBound, int upperBound){
double dl=lowerBound\*0.01;
double du=upperBound\*0.01;
for(int i=0;i<tree.size();i++)mz\[i\].clear();
for(int i=0;i<tree.size();i++){
int par;double p1,p2;
if(i==0){
sscanf(tree\[i\].c\_str(),"%lf",&p1);
p1\*=0.01;
nodes\[i\].rp=p1;
}else{
sscanf(tree\[i\].c\_str(),"%d%lf%lf",&par,&p1,&p2);
p1\*=0.01,p2\*=0.01;
nodes\[i\].prob1=p1;
nodes\[i\].prob2=p2;
mz\[par\].PB(i);
}
}
Set(vis,0);
dfs(0,0);
vector<int\> ans;
for(int i=0;i<tree.size();i++)
if(dl<nodes\[i\].rp&&nodes\[i\].rp<du)ans.PB(i);
return ans;
}
// BEGIN CUT HERE
public:
void run\_test(int Case) {
if ((Case == -1) || (Case == 0)) test\_case\_0();
if ((Case == -1) || (Case == 1)) test\_case\_1();
if ((Case == -1) || (Case == 2)) test\_case\_2();
if ((Case == -1) || (Case == 3)) test\_case\_3();
if ((Case == -1) || (Case == 4)) test\_case\_4();
if ((Case == -1) || (Case == 5)) test\_case\_5();
if ((Case == -1) || (Case == 6)) test\_case\_6();
}
private:
template <typename T> string print\_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const\_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\\"' << \*iter << "\\","; os << " }"; return os.str(); }
void verify\_case(int Case, const vector <int\> &Expected, const vector <int\> &Received) { cout << "測試案例 #" << Case << "..."; if (Expected == Received) cout << "通過" << endl; else { cout << "失敗" << endl; cout << "\\t預期: " << print\_array(Expected) << endl; cout << "\\t收到: " << print\_array(Received) << endl; } }
void test\_case\_0() {
string Arr0\[\] = {"40","0 70 10"};
vector <string\> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0\[0\])));
int Arg1 = 30;
int Arg2 = 50;
int Arr3\[\] = { 0, 1 };
vector <int\> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3\[0\])));
verify\_case(0, Arg3, getOdds(Arg0, Arg1, Arg2)); }
void test\_case\_1() {
string Arr0\[\] = {"20","2 50 50","0 50 50"};
vector <string\> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0\[0\])));
int Arg1 = 49;
int Arg2 = 51;
int Arr3\[\] = { 1, 2 };
vector <int\> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3\[0\])));
verify\_case(1, Arg3, getOdds(Arg0, Arg1, Arg2)); }
void test\_case\_2() {
string Arr0\[\] = {"10","0 99 41","1 40 3","2 91 43"};
vector <string\> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0\[0\])));
int Arg1 = 81;
int Arg2 = 88;
int Arr3\[\] = { };
vector <int\> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3\[0\])));
verify\_case(2, Arg3, getOdds(Arg0, Arg1, Arg2)); }
void test\_case\_3() {
string Arr0\[\] = {"79","0 64 52","1 70 87","0 38 99","1 24 8"};
vector <string\> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0\[0\])));
int Arg1 = 47;
int Arg2 = 81;
int Arr3\[\] = { 0, 1, 2, 3 };
vector <int\> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3\[0\])));
verify\_case(3, Arg3, getOdds(Arg0, Arg1, Arg2)); }
void test\_case\_4() {
string Arr0\[\] = {"51",
"29 58 3",
"6 56 86",
"18 97 1",
"44 99 25",
"33 69 90",
"27 67 49",
"32 15 19",
"33 1 21",
"45 12 33",
"29 24 40",
"45 86 74",
"40 30 65",
"0 18 27",
"1 90 65",
"0 47 62",
"40 81 72",
"42 25 56",
"45 16 81",
"8 94 92",
"29 41 92",
"24 4 29",
"32 56 91",
"20 16 77",
"1 35 79",
"45 77 61",
"6 50 19",
"20 69 43",
"4 6 16",
"15 55 26",
"42 73 90",
"40 8 49",
"33 16 33",
"15 95 47",
"9 66 40",
"25 80 39",
"35 72 70",
"27 10 36",
"40 36 10",
"32 2 48",
"33 44 23",
"22 51 45",
"25 8 43",
"18 32 96",
"45 41 74",
"0 51 6",
"18 48 15"};
vector <string\> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0\[0\])));
int Arg1 = 8;
int Arg2 = 82;
int Arr3\[\] = { 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 23, 24, 25, 26, 27, 28, 29, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46 };
vector <int\> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3\[0\])));
verify\_case(4, Arg3, getOdds(Arg0, Arg1, Arg2)); }
void test\_case\_5() {
string Arr0\[\] = {"40","0 70 10"};
vector <string\> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0\[0\])));
int Arg1 = 30;
int Arg2 = 50;
int Arr3\[\] = { 0, 1 };
vector <int\> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3\[0\])));
verify\_case(5, Arg3, getOdds(Arg0, Arg1, Arg2)); }
void test\_case\_6() {
string Arr0\[\] = {"40","0 70 10"};
vector <string\> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0\[0\])));
int Arg1 = 30;
int Arg2 = 50;
int Arr3\[\] = { 0, 1 };
vector <int\> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3\[0\])));
verify\_case(6, Arg3, getOdds(Arg0, Arg1, Arg2)); }
// END CUT HERE
};
// BEGIN CUT HERE
int main()
{
ProbabilityTree \_\_\_test;
\_\_\_test.run\_test(-1);
return 0;
}
// END CUT HERE