Overview
| SHA1 Hash: | c9a076d5098298a51b80bf20c2306209a3dbb2ec |
|---|---|
| Date: | 2014-01-11 10:21:30 |
| User: | kinaba |
| Comment: | 603 |
| 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/603-U/1A.cpp version [825225f39a87e55b]
> 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 #include <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class MaxMinTreeGame { public: > 23 int findend(vector <int> edges, vector <int> costs) > 24 { > 25 int N = costs.size(); > 26 vector<int> deg(N); > 27 for(int i=0; i<N-1; ++i) { > 28 deg[i+1]++; > 29 deg[edges[i]]++; > 30 } > 31 int maxLeaf = 0; > 32 for(int i=0; i<N; ++i) > 33 if(deg[i]==1) > 34 maxLeaf = max(maxLeaf, costs[i]); > 35 return maxLeaf; > 36 } > 37 }; > 38 > 39 // BEGIN CUT HERE > 40 #include <ctime> > 41 double start_time; string timer() > 42 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 43 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 44 { os << "{ "; > 45 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 46 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 47 void verify_case(const int& Expected, const int& Received) { > 48 bool ok = (Expected == Received); > 49 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 50 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 51 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 52 #define END verify_case(_, MaxMinTreeGame().findend(edges, costs));} > 53 int main(){ > 54 > 55 CASE(0) > 56 int edges_[] = {0}; > 57 vector <int> edges(edges_, edges_+sizeof(edges_)/sizeof(*edges_)); > 58 int costs_[] = {4,6}; > 59 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 60 int _ = 6; > 61 END > 62 CASE(1) > 63 int edges_[] = {0,1}; > 64 vector <int> edges(edges_, edges_+sizeof(edges_)/sizeof(*edges_)); > 65 int costs_[] = {4,6,5}; > 66 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 67 int _ = 5; > 68 END > 69 CASE(2) > 70 int edges_[] = {0,1,2,3}; > 71 vector <int> edges(edges_, edges_+sizeof(edges_)/sizeof(*edges_)); > 72 int costs_[] = {0,1,0,1,0}; > 73 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 74 int _ = 0; > 75 END > 76 CASE(3) > 77 int edges_[] = {0,0,0}; > 78 vector <int> edges(edges_, edges_+sizeof(edges_)/sizeof(*edges_)); > 79 int costs_[] = {5,1,2,3}; > 80 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 81 int _ = 3; > 82 END > 83 CASE(4) > 84 int edges_[] = {0,0}; > 85 vector <int> edges(edges_, edges_+sizeof(edges_)/sizeof(*edges_)); > 86 int costs_[] = {3,2,5}; > 87 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 88 int _ = 5; > 89 END > 90 /* > 91 CASE(6) > 92 int edges_[] = ; > 93 vector <int> edges(edges_, edges_+sizeof(edges_)/sizeof(*edges_)); > 94 int costs_[] = ; > 95 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); > 96 int _ = ; > 97 END > 98 */ > 99 } > 100 // END CUT HERE
Added SRM/603-U/2A.cpp version [9f6441ed525e874c]
> 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 #include <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 static const unsigned MODVAL = 1000000007; > 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 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 39 > 40 class PairsOfStrings { public: > 41 int getNumber(int n, int k) > 42 { > 43 set<int> ds; > 44 for(int d=1; d*d<=n; ++d) > 45 if(n%d == 0) { > 46 ds.insert(d); > 47 ds.insert(n/d); > 48 } > 49 > 50 memo.clear(); > 51 > 52 mint total = 0; > 53 for(int d: ds) > 54 total += count_unit(ds, d, k) * d; > 55 return total.val; > 56 } > 57 > 58 map<int, mint> memo; > 59 mint count_unit(const set<int>& ds, int d, int k) > 60 { > 61 if(memo.count(d)) > 62 return memo[d]; > 63 > 64 mint v = POW(k, d); > 65 for(int x: ds) { > 66 if(x>=d) > 67 break; > 68 if(d%x==0) > 69 v -= count_unit(ds, x, k); > 70 } > 71 return memo[d] = v; > 72 } > 73 }; > 74 > 75 // BEGIN CUT HERE > 76 #include <ctime> > 77 double start_time; string timer() > 78 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 79 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 80 { os << "{ "; > 81 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 82 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 83 void verify_case(const int& Expected, const int& Received) { > 84 bool ok = (Expected == Received); > 85 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 86 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 87 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 88 #define END verify_case(_, PairsOfStrings().getNumber(n, k));} > 89 int main(){ > 90 > 91 CASE(0) > 92 int n = 2; > 93 int k = 2; > 94 int _ = 6; > 95 END > 96 CASE(1) > 97 int n = 3; > 98 int k = 2; > 99 int _ = 20; > 100 END > 101 CASE(2) > 102 int n = 3; > 103 int k = 4; > 104 int _ = 184; > 105 END > 106 CASE(3) > 107 int n = 6; > 108 int k = 2; > 109 int _ = 348; > 110 END > 111 CASE(4) > 112 int n = 100; > 113 int k = 26; > 114 int _ = 46519912; > 115 END > 116 CASE(5) > 117 int n = 100000000; > 118 int k = 26; > 119 int _ = -1; > 120 END > 121 /* > 122 CASE(6) > 123 int n = ; > 124 int k = ; > 125 int _ = ; > 126 END > 127 */ > 128 } > 129 // END CUT HERE