水題，只要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 << "Test Case #" << Case << "..."; if (Expected == Received) cout << "PASSED" << endl; else { cout << "FAILED" << endl; cout << "\tExpected: " << print_array(Expected) << endl; cout << "\tReceived: " << 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
留言
張貼留言