1 // BEGIN CUT HERE  2 /*  3   4 */  5 // END CUT HERE  6 #line 7 "CandleTimerEasy.cpp"  7 #include <cstdlib>  8 #include <cctype>  9 #include <cstring> 10 #include <cstdio> 11 #include <cmath> 12 #include <algorithm> 13 #include <vector> 14 #include <string> 15 #include <iostream> 16 #include <sstream> 17 #include <map> 18 #include <set> 19 #include <queue> 20 #include <stack> 21 #include <fstream> 22 #include <numeric> 23 #include <iomanip> 24 #include <bitset> 25 #include <list> 26 #include <stdexcept> 27 #include <functional> 28 #include <utility> 29 #include <ctime> 30 using namespace std; 31  32 #define PB push_back 33 #define MP make_pair 34  35 #define REP(i,n) for(i=0;i<(n);++i) 36 #define FOR(i,l,h) for(i=(l);i<=(h);++i) 37 #define FORD(i,h,l) for(i=(h);i>=(l);--i) 38  39 typedef vector<int> VI; 40 typedef vector<string> VS; 41 typedef vector<double> VD; 42 typedef long long LL; 43 typedef pair<int,int> PII; 44  45 int hs[30]; 46 struct node{ 47   int ne,w; 48   node(int _ne ,int _w) 49   { 50      ne = _ne ;  51      w = _w;  52   } 53 }; 54 vector<node> mp[30]; 55 vector<int> leaf; 56 int ans[41*1000]; 57 int ti[30]; 58 class CandleTimerEasy 59 { 60         public: 61         int n ; 62         int sum;     63         void dfs(int k ,int fa , int t) 64         { 65     //        printf("%d %d %d\n",k,fa,t); 66                if(t < ti[k]) 67             { 68                 ti[k] = t; 69  70             } 71             int num = mp[k].size(); 72             for(int i = 0 ;i < num ;i ++) 73             { 74              if(mp[k][i].ne != fa) 75                dfs(mp[k][i].ne,k,t + mp[k][i].w);       76             } 77         } 78         void solve(vector<int> A,vector<int> B,vector<int> len) 79         { 80           int k = leaf.size(); 81           int num = (1 << k) -1; 82           //printf("********%d\n",ti[0]); 83           memset(ans,0,sizeof(ans)); 84            85           for(int i = 0 ;i <= num ; i ++) 86           { 87               for(int j = 0 ;j <= n ;j ++) 88               { 89                ti[j] = 1e8; 90               } 91               int hehe = 0 ;  92               for(int j = 0 ;j < k ;j ++) 93               { 94                  if((i >> j ) & 1) 95                  { 96                 //    printf("%d ",leaf[j]); 97                     dfs(leaf[j],-1,0); 98                     hehe ++ ; 99                  }100               }101              // puts("");102               if(hehe == 0 )103                   continue;104               int mx = 0 ;105               /*for(int j = 0 ;j <= n;j ++)106                   printf("%d ",ti[j]);107               printf("\n");108               */109               for(int j = 0 ;j < n;j ++)110               {111                   int tt; 112                   if(abs(ti[A[j]] - ti[B[j]]) < len[j])113                   {114                     115                    int  tmi = min(ti[A[j]],ti[B[j]]); 116                    int  tmx = max(ti[A[j]],ti[B[j]]);117                    tt = tmx*2 + (len[j]-(tmx-tmi));118                   }else{119                     tt = min(ti[A[j]],ti[B[j]]) + len[j];120                     tt *= 2;121                   }122                 //  printf("%.1lf ",tt*1.0/2);123                   //printf("%d\n",tt);124                   mx = max(tt,mx);125               }126               //printf("***%.1lf\n",mx*1.0/2);127              // printf("%d\n",mx);128               if(ans[mx] == 0 )129               {130                   ans[mx] ++ ;131                   sum ++ ; 132               }133           }134         }135         int differentTime(vector <int> A, vector <int> B, vector <int> len)136         {137            n = A.size();138            sum = 0 ;139            leaf.clear();140            memset(hs,0,sizeof(hs));141            for(int i = 0 ;i <= 20 ;i ++)142                mp[i].clear();143            for(int i = 0;i < n; i ++)144            {145               mp[A[i]].push_back(node(B[i],len[i]));146               mp[B[i]].push_back(node(A[i],len[i]));147               hs[A[i]] ++ ; 148               hs[B[i]] ++ ; 149            }150 151            for(int i = 0;i <= n;i ++ )152            {153               if(hs[i] == 1 )154                 leaf.push_back(i);            155            }156            solve(A,B,len);157            return sum;158         }159          160 // BEGIN CUT HERE161     public:162     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(); }163     private:164     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(); }165     void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << ‘\"‘ << endl; cerr << "\tReceived: \"" << Received << ‘\"‘ << endl; } }166     void test_case_0() { int Arr0[] = {0,1}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1,2}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {10,1}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 2; verify_case(0, Arg3, differentTime(Arg0, Arg1, Arg2)); }167     void test_case_1() { int Arr0[] = {0,0,0}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1,2,3}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {1,1,1}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 2; verify_case(1, Arg3, differentTime(Arg0, Arg1, Arg2)); }168     void test_case_2() { int Arr0[] = {0,0,0}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1,2,3}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {1,2,3}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 4; verify_case(2, Arg3, differentTime(Arg0, Arg1, Arg2)); }169     void test_case_3() { int Arr0[] = {0,1,1,2,3,3,2,4}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1,2,3,4,5,6,7,8}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {5,3,2,4,6,8,7,1}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 7; verify_case(3, Arg3, differentTime(Arg0, Arg1, Arg2)); }170     void test_case_4() { int Arr0[] = {0,0,0,0}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1,2,3,4}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {123,456,789,1000}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 8; verify_case(4, Arg3, differentTime(Arg0, Arg1, Arg2)); }171     void test_case_5() { int Arr0[] = {0}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {1000}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 2; verify_case(5, Arg3, differentTime(Arg0, Arg1, Arg2)); }172 173 // END CUT HERE174 175 };176 177 // BEGIN CUT HERE178 int main()179 {180         CandleTimerEasy ___test;181         ___test.run_test(-1);182         return 0;183 }184 // END CUT HERE