Overview
| SHA1 Hash: | 155c399d58f8ec3efb06eff4acba55ba6d38ea8b |
|---|---|
| Date: | 2012-12-08 16:59:00 |
| User: | kinaba |
| Comment: | 562 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/562-U/1A-U.cpp version [81e3457a1a1154c2]
1 +#include <iostream> 2 +#include <sstream> 3 +#include <iomanip> 4 +#include <vector> 5 +#include <string> 6 +#include <map> 7 +#include <set> 8 +#include <algorithm> 9 +#include <numeric> 10 +#include <iterator> 11 +#include <functional> 12 +#include <complex> 13 +#include <queue> 14 +#include <stack> 15 +#include <cmath> 16 +#include <cassert> 17 +using namespace std; 18 +typedef long long LL; 19 +typedef long double LD; 20 +typedef complex<LD> CMP; 21 + 22 +class PastingPaintingDivOne { public: 23 + vector<long long> countColors(vector <string> c, int T) 24 + { 25 + int H = c.size(); 26 + int W = c[0].size(); 27 + 28 + int TR = min(T, 50+T%50); 29 + vector<string> shifted(H+TR+50, string(W+H, '.')); 30 + 31 + // TR 32 + for(int i=0; i<TR; ++i) 33 + for(int y=0; y<H; ++y) 34 + for(int x=0; x<W; ++x) 35 + if(c[y][x] != '.') 36 + shifted[i+y][x+H-1-y] = c[y][x]; 37 + 38 + LL r=0, g=0, b=0; 39 + for(int y=0; y<shifted.size(); ++y) 40 + for(int x=0; x<shifted[y].size(); ++x) 41 + if(shifted[y][x]=='R') r++; 42 + else if(shifted[y][x]=='G') g++; 43 + else if(shifted[y][x]=='B') b++; 44 + 45 + // 50 more 46 + for(int i=TR; i<TR+50; ++i) 47 + for(int y=0; y<H; ++y) 48 + for(int x=0; x<W; ++x) 49 + if(c[y][x] != '.') 50 + shifted[i+y][x+H-1-y] = c[y][x]; 51 + 52 + LL rr=0, gg=0, bb=0; 53 + for(int y=0; y<shifted.size(); ++y) 54 + for(int x=0; x<shifted[y].size(); ++x) 55 + if(shifted[y][x]=='R') rr++; 56 + else if(shifted[y][x]=='G') gg++; 57 + else if(shifted[y][x]=='B') bb++; 58 + 59 + vector<LL> answer; 60 + answer.push_back((rr-r)*(T-TR)/50 + r); 61 + answer.push_back((gg-g)*(T-TR)/50 + g); 62 + answer.push_back((bb-b)*(T-TR)/50 + b); 63 + return answer; 64 + } 65 +}; 66 + 67 +// BEGIN CUT HERE 68 +#include <ctime> 69 +double start_time; string timer() 70 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 71 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 72 + { os << "{ "; 73 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 74 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 75 +void verify_case(const vector<long long>& Expected, const vector<long long>& Received) { 76 + bool ok = (Expected == Received); 77 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 78 + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } 79 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 80 +#define END verify_case(_, PastingPaintingDivOne().countColors(clipboard, T));} 81 +int main(){ 82 + 83 +CASE(0) 84 + string clipboard_[] = { 85 +"..G", 86 +"R..", 87 +"BG." 88 +}; 89 + vector <string> clipboard(clipboard_, clipboard_+sizeof(clipboard_)/sizeof(*clipboard_)); 90 + int T = 3; 91 + long long __[] = {3, 4, 3 }; 92 + vector<long long> _(__, __+sizeof(__)/sizeof(*__)); 93 +END 94 +CASE(1) 95 + string clipboard_[] = { 96 +"R...", 97 +"....", 98 +"....", 99 +"...R" 100 +}; 101 + vector <string> clipboard(clipboard_, clipboard_+sizeof(clipboard_)/sizeof(*clipboard_)); 102 + int T = 2; 103 + long long __[] = {4, 0, 0 }; 104 + vector<long long> _(__, __+sizeof(__)/sizeof(*__)); 105 +END 106 +CASE(2) 107 + string clipboard_[] = {"RGB"}; 108 + vector <string> clipboard(clipboard_, clipboard_+sizeof(clipboard_)/sizeof(*clipboard_)); 109 + int T = 100000; 110 + long long __[] = {100000, 100000, 100000 }; 111 + vector<long long> _(__, __+sizeof(__)/sizeof(*__)); 112 +END 113 +CASE(3) 114 + string clipboard_[] = {"."}; 115 + vector <string> clipboard(clipboard_, clipboard_+sizeof(clipboard_)/sizeof(*clipboard_)); 116 + int T = 1000000000; 117 + long long __[] = {0, 0, 0 }; 118 + vector<long long> _(__, __+sizeof(__)/sizeof(*__)); 119 +END 120 +CASE(4) 121 + string clipboard_[] = { 122 +"RB.", 123 +".G." 124 +} 125 +; 126 + vector <string> clipboard(clipboard_, clipboard_+sizeof(clipboard_)/sizeof(*clipboard_)); 127 + int T = 100; 128 + long long __[] = {100, 1, 100 }; 129 + vector<long long> _(__, __+sizeof(__)/sizeof(*__)); 130 +END 131 +CASE(5) 132 + string clipboard_[] = { 133 +"..........G..........", 134 +".........G.G.........", 135 +"........G...G........", 136 +".......G.....G.......", 137 +"......G..B.B..G......", 138 +".....G...B.B...G.....", 139 +"....G...........G....", 140 +"...G...R.....R...G...", 141 +"..G.....RRRRRR....G..", 142 +".G..........RR.....G.", 143 +"GGGGGGGGGGGGGGGGGGGGG" 144 +}; 145 + vector <string> clipboard(clipboard_, clipboard_+sizeof(clipboard_)/sizeof(*clipboard_)); 146 + int T = 1000000000; 147 + long long __[] = {2000000018, 17000000048, 2000000005 }; 148 + vector<long long> _(__, __+sizeof(__)/sizeof(*__)); 149 +END 150 +/* 151 +CASE(6) 152 + string clipboard_[] = ; 153 + vector <string> clipboard(clipboard_, clipboard_+sizeof(clipboard_)/sizeof(*clipboard_)); 154 + int T = ; 155 + long long __[] = ; 156 + vector<long long> _(__, __+sizeof(__)/sizeof(*__)); 157 +END 158 +CASE(7) 159 + string clipboard_[] = ; 160 + vector <string> clipboard(clipboard_, clipboard_+sizeof(clipboard_)/sizeof(*clipboard_)); 161 + int T = ; 162 + long long __[] = ; 163 + vector<long long> _(__, __+sizeof(__)/sizeof(*__)); 164 +END 165 +*/ 166 +} 167 +// END CUT HERE
Added SRM/562-U/1B-U.cpp version [ce107d8a36905d31]
1 +#include <iostream> 2 +#include <sstream> 3 +#include <iomanip> 4 +#include <vector> 5 +#include <string> 6 +#include <map> 7 +#include <set> 8 +#include <algorithm> 9 +#include <numeric> 10 +#include <iterator> 11 +#include <functional> 12 +#include <complex> 13 +#include <queue> 14 +#include <stack> 15 +#include <cmath> 16 +#include <cassert> 17 +using namespace std; 18 +typedef long long LL; 19 +typedef complex<double> CMP; 20 + 21 +class CheckerFreeness { public: 22 + string isFree(vector <string> whiteX, vector <string> whiteY, vector <string> blackX, vector <string> blackY) 23 + { 24 + stringstream swx(accumulate(whiteX.begin(), whiteX.end(), string(""))); 25 + stringstream swy(accumulate(whiteY.begin(), whiteY.end(), string(""))); 26 + stringstream sbx(accumulate(blackX.begin(), blackX.end(), string(""))); 27 + stringstream sby(accumulate(blackY.begin(), blackY.end(), string(""))); 28 + 29 + vector<CMP> w; 30 + for(int x,y; (swx>>x)&&(swy>>y); ) 31 + w.push_back(CMP(x,y)); 32 + 33 + vector<CMP> b; 34 + for(int x,y; (sbx>>x)&&(sby>>y); ) 35 + b.push_back(CMP(x,y)); 36 + 37 + return has_checker(w,b) ? "NO" : "YES"; 38 + } 39 + 40 + bool has_checker(const vector<CMP>& w, const vector<CMP>& b) 41 + { 42 + for(int i=0; i<w.size(); ++i) 43 + for(int k=i+1; k<w.size(); ++k) 44 + if(has_crosser(w[i], w[k], b)) 45 + return true; 46 + return false; 47 + } 48 + 49 + bool has_crosser(CMP a, CMP b, const vector<CMP>& ps) 50 + { 51 + vector<double> arg_a, arg_b; 52 + vector<CMP> qs; 53 + for(int i=0; i<ps.size(); ++i) 54 + { 55 + double d = arg( (ps[i]-a)/(b-a) ); 56 + if(d > 0) { 57 + arg_a.push_back(d); 58 + d = arg( (ps[i]-b)/(b-a) ); 59 + arg_b.push_back(d); 60 + } else { 61 + qs.push_back(ps[i]); 62 + } 63 + } 64 + sort(arg_a.begin(), arg_a.end()); 65 + sort(arg_b.begin(), arg_b.end()); 66 + for(int i=0; i<qs.size(); ++i) 67 + { 68 + CMP q = qs[i]; 69 + double aMax = arg((a-q) / (b-a)); 70 + double bMax = arg((b-q) / (b-a)); 71 + int aNum = lower_bound(arg_a.begin(), arg_a.end(), aMax) - arg_a.begin(); 72 + int bNum = lower_bound(arg_b.begin(), arg_b.end(), bMax) - arg_b.begin(); 73 + if(aNum != bNum) 74 + return true; 75 + } 76 + return false; 77 + } 78 +}; 79 + 80 +// BEGIN CUT HERE 81 +#include <ctime> 82 +double start_time; string timer() 83 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 84 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 85 + { os << "{ "; 86 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 87 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 88 +void verify_case(const string& Expected, const string& Received) { 89 + bool ok = (Expected == Received); 90 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 91 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 92 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 93 +#define END verify_case(_, CheckerFreeness().isFree(whiteX, whiteY, blackX, blackY));} 94 +int main(){ 95 + 96 +CASE(0) 97 + string whiteX_[] = {"1 2"}; 98 + vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX_)); 99 + string whiteY_[] = {"2 1"}; 100 + vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY_)); 101 + string blackX_[] = {"1 2"}; 102 + vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX_)); 103 + string blackY_[] = {"1 2"}; 104 + vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY_)); 105 + string _ = "NO"; 106 +END 107 +CASE(1) 108 + string whiteX_[] = {"2", "5", "3", " ", "1", "7", "3"}; 109 + vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX_)); 110 + string whiteY_[] = {"180 254"}; 111 + vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY_)); 112 + string blackX_[] = {"32", "5 1", "42"}; 113 + vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX_)); 114 + string blackY_[] = {"462 423"}; 115 + vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY_)); 116 + string _ = "YES"; 117 +END 118 +CASE(2) 119 + string whiteX_[] = {"1 10000000 9999999"}; 120 + vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX_)); 121 + string whiteY_[] = {"1 9999999 1"}; 122 + vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY_)); 123 + string blackX_[] = {"2 5000000 9999998"}; 124 + vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX_)); 125 + string blackY_[] = {"2 5000001 9999999"}; 126 + vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY_)); 127 + string _ = "YES"; 128 +END 129 +CASE(3) 130 + string whiteX_[] = {"1"}; 131 + vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX_)); 132 + string whiteY_[] = {"2"}; 133 + vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY_)); 134 + string blackX_[] = {"3"}; 135 + vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX_)); 136 + string blackY_[] = {"4"}; 137 + vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY_)); 138 + string _ = "YES"; 139 +END 140 +CASE(4) 141 + string whiteX_[] = {"6115 9723 3794 2275 2268 2702 3657 915 7953 2743 7" 142 +,"716 9645 2547 9490 9365 326 6601 5215 6771 7153 72" 143 +,"93 5922 714 2258 4369 9524 302 8417 6620 1143"}; 144 + vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX_)); 145 + string whiteY_[] = {"621 1611 7140 503 5345 7202 681 4908 2510 5908 279" 146 +,"6 6286 6873 6682 9197 6710 8517 1913 7784 8533 665" 147 +,"4 446 3561 7241 6168 2025 4739 9501 5340 6446"}; 148 + vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY_)); 149 + string blackX_[] = {"6833 131 4151 1776 1959 7210 1903 6107 598 6220 94" 150 +,"24 5374 6718 2919 6068 6644 5070 710 7121 1630 370" 151 +,"3 1051 5739 9294 8798 3371 8107 2130 6608 534"}; 152 + vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX_)); 153 + string blackY_[] = {"7496 2412 2801 3473 5810 2714 7853 9714 5470 3558 " 154 +,"8143 2391 8234 7292 9311 1636 8978 1107 2262 9175 " 155 +,"7259 8842 5294 7209 2317 3825 3413 820 3774 5393"}; 156 + vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY_)); 157 + string _ = "NO"; 158 +END 159 +CASE(5) 160 + string whiteX_[] = {"219211 1996214 1706774 3634920 909831 1774128 8503" 161 +,"52 2233050 2099138 3380396 1128982 3682525 1483700" 162 +," 763080 487867 8203 1791027 463556 1103323 1406861" 163 +," 6374234 760949 4340236 727393 2073832 1289052 103" 164 +,"8147 4448130 151066 412440 1068735 377239 2677933 " 165 +,"1299598 339843 289973 3707319 555280 230418 431719"}; 166 + vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX_)); 167 + string whiteY_[] = {"1638083 5698739 3105504 9726902 9745795 5049444 15" 168 +,"80592 3952120 6606668 7460527 7239299 8726128 4913" 169 +,"547 6264100 5701660 8865937 4969114 8014845 327236" 170 +,"1 6389154 9739755 2561669 9412417 5452337 3150506 " 171 +,"5832197 1571976 8779325 3306446 948271 5133709 949" 172 +,"394 6919798 7525636 3568024 6833196 9237472 733313" 173 +,"1 9939064 9720014"}; 174 + vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY_)); 175 + string blackX_[] = {"5860334 8007503 7455523 4864927 9573526 2718360 81" 176 +,"12104 6684287 9921506 4840886 5415948 3451454 5320" 177 +,"996 9268757 9261724 8254668 2292750 8035828 233352" 178 +,"1 7676906 5234406 8533320 6562751 4884098 4971897 " 179 +,"5569360 8519168 3100295 9351613 7733878 7579030 32" 180 +,"46775 7297460 8370542 7099759 5782969 2978083 3390" 181 +,"488 7482758 1332401 6094629 9717305 5503121 572842" 182 +,"1 4903563 6331656 2867455 3410007 7751527 7228221 " 183 +,"4111694 5171296 6847697 4601273 7599828 5515929 94" 184 +,"60593 9332762 5389080 4512091 8668538 5711743 5838" 185 +,"534 4825079 8145628 3810005 2964724 5594550 785748" 186 +,"3 6283769"}; 187 + vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX_)); 188 + string blackY_[] = {"5911694 8009943 212555 5838688 9896256 607434 5857" 189 +,"663 4616750 1477573 7168026 3090917 4379806 326465" 190 +,"7 4189076 2104028 3279691 94211 8503556 78457 4394" 191 +,"360 3344176 3223317 2624498 4883494 1532240 732937" 192 +,"1 1518674 1353567 892134 5536454 8527392 2603965 6" 193 +,"623264 8830827 2030444 3002706 83058 4475866 20876" 194 +,"25 1790695 4034441 5409379 3571098 4600050 736561 " 195 +,"250475 3733256 3011439 2144994 4523046 3119883 607" 196 +,"582 8361403 6525451 7518329 926803 4884524 8424659" 197 +," 7088689 5762049 9532481 4914186 7314621 4339084 3" 198 +,"741685 3837953 3177252 612550 9688871 5872931"}; 199 + vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY_)); 200 + string _ = "YES"; 201 +END 202 +/* 203 +CASE(6) 204 + string whiteX_[] = ; 205 + vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX_)); 206 + string whiteY_[] = ; 207 + vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY_)); 208 + string blackX_[] = ; 209 + vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX_)); 210 + string blackY_[] = ; 211 + vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY_)); 212 + string _ = ; 213 +END 214 +CASE(7) 215 + string whiteX_[] = ; 216 + vector <string> whiteX(whiteX_, whiteX_+sizeof(whiteX_)/sizeof(*whiteX_)); 217 + string whiteY_[] = ; 218 + vector <string> whiteY(whiteY_, whiteY_+sizeof(whiteY_)/sizeof(*whiteY_)); 219 + string blackX_[] = ; 220 + vector <string> blackX(blackX_, blackX_+sizeof(blackX_)/sizeof(*blackX_)); 221 + string blackY_[] = ; 222 + vector <string> blackY(blackY_, blackY_+sizeof(blackY_)/sizeof(*blackY_)); 223 + string _ = ; 224 +END 225 +*/ 226 +} 227 +// END CUT HERE
Added SRM/562-U/1C-U.cpp version [f4634643344316b4]
1 +#include <iostream> 2 +#include <sstream> 3 +#include <iomanip> 4 +#include <vector> 5 +#include <string> 6 +#include <map> 7 +#include <set> 8 +#include <algorithm> 9 +#include <numeric> 10 +#include <iterator> 11 +#include <functional> 12 +#include <complex> 13 +#include <queue> 14 +#include <stack> 15 +#include <cmath> 16 +#include <cassert> 17 +using namespace std; 18 +typedef long long LL; 19 +typedef long double LD; 20 +typedef complex<LD> CMP; 21 + 22 +static const unsigned MODVAL = 1000000009; 23 +struct mint 24 +{ 25 + unsigned val; 26 + mint():val(0){} 27 + mint(int x):val(x%MODVAL) {} 28 + mint(unsigned x):val(x%MODVAL) {} 29 + mint(LL x):val(x%MODVAL) {} 30 +}; 31 +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } 32 +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } 33 +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } 34 +mint operator+(mint x, mint y) { return x+=y; } 35 +mint operator-(mint x, mint y) { return x-=y; } 36 +mint operator*(mint x, mint y) { return x*=y; } 37 + 38 +vector<mint> FAC_(1,1); 39 +mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[n]; } 40 + 41 +// nCk :: O(1) time, O(n^2) space. 42 +vector< vector<mint> > CP_; 43 +mint C(LL n, LL k) { 44 + while( CP_.size() <= n ) { 45 + int nn = CP_.size(); 46 + CP_.push_back(vector<mint>(nn+1,1)); 47 + for(int kk=1; kk<nn; ++kk) 48 + CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; 49 + } 50 + return k<0 || n<k ? 0 : CP_[n][k]; 51 +} 52 + 53 +class InducedSubgraphs { public: 54 + int getCount(vector <int> edge1, vector <int> edge2, int k) 55 + { 56 + int N = edge1.size()+1; 57 + vector< vector<int> > G(N); 58 + for(int i=0; i<edge1.size(); ++i) 59 + { 60 + int v = edge1[i], u = edge2[i]; 61 + G[v].push_back(u); 62 + G[u].push_back(v); 63 + } 64 + return solve(G, N, k).val; 65 + } 66 + 67 + mint solve(const vector<vector<int> >& G, int N, int K) 68 + { 69 + mint total = 0; 70 + for(int root=0; root<N; ++root) 71 + total += solve_rooted(G, N, K, root); 72 + return total; 73 + } 74 + 75 + mint solve_rooted(const vector<vector<int> >& G, int N, int K, int root) 76 + { 77 + memo.clear(); 78 + 79 + int pre = -1, cur = root; 80 + for(int below=N,above=0 ;; --below,++above) 81 + if(below <= K) { 82 + mint b = rec(G, pre, cur).second; 83 + mint a = (above>=K-1 ? mint(1) : FAC(K-above)); 84 + return b*a; 85 + } else { 86 + if((pre==-1 && G[cur].size()>=2) || G[cur].size()>=3) { 87 + // fill_branch 88 +/* 89 + vector< pair<int,int> > v_sz; 90 + for(int k=0; k<G[cur].size(); ++k) if(G[cur][k] != pre) 91 + v_sz.push_back(make_pair(G[cur][k], rec(G, cur, G[cur][k]))); 92 + 93 + int total_size = 0; 94 + for(int k=0; k<v_sz.size(); ++k) 95 + total_size += v_sz[k].second; 96 + for(int k=0; k<v_sz.size(); ++k) 97 + if( v_sz[k].second+1 <= K ) 98 +*/ 99 + return 0; 100 + } 101 + 102 + int nex = (G[cur][0]!=pre ? G[cur][0] : G[cur][1]); 103 + pre = cur; 104 + cur = nex; 105 + } 106 + } 107 + 108 + // (size, number of toplofical sorting). 109 + map<int, pair<int,mint> > memo; 110 + pair<int,mint> rec(const vector<vector<int> >& G, int pre, int cur) 111 + { 112 + if(memo.count(cur)) 113 + return memo[cur]; 114 + 115 + vector< pair<int,mint> > children; 116 + for(int i=0; i<G[cur].size(); ++i) if(G[cur][i] != pre) 117 + children.push_back(rec(G, cur, G[cur][i])); 118 + 119 + mint pat = 1; 120 + int size = 0; 121 + for(int i=0; i<children.size(); ++i) { 122 + size += children[i].first; 123 + pat = pat * C(size, children[i].first) * children[i].second; 124 + } 125 + return memo[cur] = make_pair(size+1, pat); 126 + } 127 +}; 128 + 129 +// BEGIN CUT HERE 130 +#include <ctime> 131 +double start_time; string timer() 132 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 133 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 134 + { os << "{ "; 135 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 136 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 137 +void verify_case(const int& Expected, const int& Received) { 138 + bool ok = (Expected == Received); 139 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 140 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 141 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 142 +#define END verify_case(_, InducedSubgraphs().getCount(edge1, edge2, k));} 143 +int main(){ 144 + 145 +CASE(0) 146 + int edge1_[] = {0, 1}; 147 + vector <int> edge1(edge1_, edge1_+sizeof(edge1_)/sizeof(*edge1_)); 148 + int edge2_[] = {1, 2}; 149 + vector <int> edge2(edge2_, edge2_+sizeof(edge2_)/sizeof(*edge2_)); 150 + int k = 2; 151 + int _ = 2; 152 +END 153 +CASE(1) 154 + int edge1_[] = {0, 1, 3}; 155 + vector <int> edge1(edge1_, edge1_+sizeof(edge1_)/sizeof(*edge1_)); 156 + int edge2_[] = {2, 2, 2}; 157 + vector <int> edge2(edge2_, edge2_+sizeof(edge2_)/sizeof(*edge2_)); 158 + int k = 3; 159 + int _ = 12; 160 +END 161 +CASE(2) 162 + int edge1_[] = {5, 0, 1, 2, 2}; 163 + vector <int> edge1(edge1_, edge1_+sizeof(edge1_)/sizeof(*edge1_)); 164 + int edge2_[] = {0, 1, 2, 4, 3}; 165 + vector <int> edge2(edge2_, edge2_+sizeof(edge2_)/sizeof(*edge2_)); 166 + int k = 3; 167 + int _ = 4; 168 +END 169 +CASE(3) 170 + int edge1_[] = {0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6}; 171 + vector <int> edge1(edge1_, edge1_+sizeof(edge1_)/sizeof(*edge1_)); 172 + int edge2_[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}; 173 + vector <int> edge2(edge2_, edge2_+sizeof(edge2_)/sizeof(*edge2_)); 174 + int k = 11; 175 + int _ = 481904640; 176 +END 177 +CASE(4) 178 + int edge1_[] = {5, 9, 4, 10, 10, 0, 7, 6, 2, 1, 11, 8} 179 +; 180 + vector <int> edge1(edge1_, edge1_+sizeof(edge1_)/sizeof(*edge1_)); 181 + int edge2_[] = {0, 0, 10, 3, 0, 6, 1, 1, 12, 12, 7, 11} 182 +; 183 + vector <int> edge2(edge2_, edge2_+sizeof(edge2_)/sizeof(*edge2_)); 184 + int k = 6; 185 + int _ = 800; 186 +END 187 +CASE(5) 188 + int edge1_[] = {0, 5, 1, 0, 2, 3, 5} 189 +; 190 + vector <int> edge1(edge1_, edge1_+sizeof(edge1_)/sizeof(*edge1_)); 191 + int edge2_[] = {4, 7, 0, 6, 7, 5, 0} 192 +; 193 + vector <int> edge2(edge2_, edge2_+sizeof(edge2_)/sizeof(*edge2_)); 194 + int k = 3; 195 + int _ = 0; 196 +END 197 +CASE(6) 198 + int edge1_[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; 199 + vector <int> edge1(edge1_, edge1_+sizeof(edge1_)/sizeof(*edge1_)); 200 + int edge2_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}; 201 + vector <int> edge2(edge2_, edge2_+sizeof(edge2_)/sizeof(*edge2_)); 202 + int k = 1; 203 + int _ = 890964601; 204 +END 205 +/* 206 +CASE(7) 207 + int edge1_[] = ; 208 + vector <int> edge1(edge1_, edge1_+sizeof(edge1_)/sizeof(*edge1_)); 209 + int edge2_[] = ; 210 + vector <int> edge2(edge2_, edge2_+sizeof(edge2_)/sizeof(*edge2_)); 211 + int k = ; 212 + int _ = ; 213 +END 214 +CASE(8) 215 + int edge1_[] = ; 216 + vector <int> edge1(edge1_, edge1_+sizeof(edge1_)/sizeof(*edge1_)); 217 + int edge2_[] = ; 218 + vector <int> edge2(edge2_, edge2_+sizeof(edge2_)/sizeof(*edge2_)); 219 + int k = ; 220 + int _ = ; 221 +END 222 +*/ 223 +} 224 +// END CUT HERE