Overview
| SHA1 Hash: | 50077c1ac17a408373ad4534531f8fb21e51b9c4 |
|---|---|
| Date: | 2014-05-29 07:03:50 |
| User: | kinaba |
| Comment: | 622 |
| 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/622-U/1A.cpp version [e1135cea5e1b761e]
> 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 BuildingRoutes { public: > 23 int build(vector <string> dist, int T) > 24 { > 25 const int N = dist.size(); > 26 vector<vector<int>> use(N, vector<int>(N, 0)); > 27 > 28 vector<vector<int>> d(N, vector<int>(N)); > 29 for(int s=0; s<N; ++s) > 30 for(int t=0; t<N; ++t) > 31 d[s][t] = dist[s][t] - '0'; > 32 for(int k=0; k<N; ++k) > 33 for(int i=0; i<N; ++i) > 34 for(int j=0; j<N; ++j) > 35 d[i][j] = min(d[i][j], d[i][k]+d[k][j]); > 36 > 37 for(int s=0; s<N; ++s) > 38 for(int t=0; t<N; ++t) > 39 for(int a=0; a<N; ++a) > 40 for(int b=0; b<N; ++b) if(a!=b) > 41 if(d[s][a]+(dist[a][b]-'0')+d[b][t] == d[s][t]) > 42 use[a][b] ++; > 43 > 44 int total = 0; > 45 for(int s=0; s<N; ++s) > 46 for(int t=0; t<N; ++t) > 47 if(use[s][t] >= T) > 48 total += dist[s][t] - '0'; > 49 return total; > 50 } > 51 }; > 52 > 53 // BEGIN CUT HERE > 54 #include <ctime> > 55 double start_time; string timer() > 56 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 57 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 58 { os << "{ "; > 59 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 60 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 61 void verify_case(const int& Expected, const int& Received) { > 62 bool ok = (Expected == Received); > 63 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 64 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 65 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 66 #define END verify_case(_, BuildingRoutes().build(dist, T));} > 67 int main(){ > 68 > 69 CASE(0) > 70 string dist_[] = {"011", > 71 "101", > 72 "110"}; > 73 vector <string> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); > 74 int T = 1; > 75 int _ = 6; > 76 END > 77 CASE(1) > 78 string dist_[] = {"033", > 79 "309", > 80 "390"}; > 81 vector <string> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); > 82 int T = 1; > 83 int _ = 12; > 84 END > 85 CASE(2) > 86 string dist_[] = {"0123", > 87 "1023", > 88 "1203", > 89 "1230"}; > 90 vector <string> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); > 91 int T = 2; > 92 int _ = 5; > 93 END > 94 CASE(3) > 95 string dist_[] = {"05789654", > 96 "10347583", > 97 "65085479", > 98 "55602398", > 99 "76590934", > 100 "57939045", > 101 "12345608", > 102 "68647640"}; > 103 vector <string> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); > 104 int T = 3; > 105 int _ = 40; > 106 END > 107 /* > 108 CASE(4) > 109 string dist_[] = ; > 110 vector <string> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); > 111 int T = ; > 112 int _ = ; > 113 END > 114 CASE(5) > 115 string dist_[] = ; > 116 vector <string> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); > 117 int T = ; > 118 int _ = ; > 119 END > 120 */ > 121 } > 122 // END CUT HERE
Added SRM/622-U/1B.cpp version [464024997191202d]
> 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 Ethernet { public: > 23 int connect(vector <int> parent, vector <int> dist, int maxDist) > 24 { > 25 int N = parent.size() + 1; > 26 vector<vector<pair<int,int>>> child(N); > 27 for(int i=0; i<parent.size(); ++i) > 28 child[parent[i]].emplace_back(i+1, dist[i]); > 29 auto cc = rec(0, child, maxDist); > 30 return cc.first + 1; > 31 } > 32 > 33 // (colors / critical path) > 34 pair<int, int> rec(int v, const vector<vector<pair<int,int>>>& child, in > 35 { > 36 if(child[v].empty()) > 37 return make_pair(0, 0); > 38 > 39 int colors = 0; > 40 vector<int> cps; > 41 for(auto& ue: child[v]) { > 42 int u = ue.first; > 43 int e = ue.second; > 44 auto cd = rec(u, child, maxDist); > 45 int c = cd.first; > 46 int d = cd.second; > 47 colors += c; > 48 if(e+d > maxDist) > 49 colors ++; > 50 else > 51 cps.push_back(e + d); > 52 } > 53 > 54 if(cps.empty()) > 55 return make_pair(colors, 0); > 56 > 57 sort(cps.rbegin(), cps.rend()); > 58 if(cps.size() > 1 && cps[0]+cps[1] > maxDist) > 59 for(int i=0; i<cps.size(); ++i) > 60 if(i+1==cps.size() || cps[i]+cps[i+1] <= maxDist > 61 return make_pair(colors+i, cps[i]); > 62 > 63 // no new color needed. > 64 return make_pair(colors, cps[0]); > 65 } > 66 }; > 67 > 68 // BEGIN CUT HERE > 69 #include <ctime> > 70 double start_time; string timer() > 71 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 72 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 73 { os << "{ "; > 74 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 75 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 76 void verify_case(const int& Expected, const int& Received) { > 77 bool ok = (Expected == Received); > 78 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 79 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 80 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 81 #define END verify_case(_, Ethernet().connect(parent, dist, maxDist));} > 82 int main(){ > 83 CASE(2) > 84 int parent_[] = {0,1,2,3,4,5}; > 85 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 86 int dist_[] = {1,2,3,4,5,6}; > 87 vector <int> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); > 88 int maxDist = 6; > 89 int _ = 3; > 90 END > 91 CASE(0) > 92 int parent_[] = {0,0,0}; > 93 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 94 int dist_[] = {1,1,1}; > 95 vector <int> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); > 96 int maxDist = 2; > 97 int _ = 1; > 98 END > 99 CASE(1) > 100 int parent_[] = {0,0,0,0,0,0,0}; > 101 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 102 int dist_[] = {1,2,3,4,5,6,7}; > 103 vector <int> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); > 104 int maxDist = 8; > 105 int _ = 4; > 106 END > 107 CASE(3) > 108 int parent_[] = {0,0,0,1,1}; > 109 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 110 int dist_[] = {1,1,1,1,1}; > 111 vector <int> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); > 112 int maxDist = 2; > 113 int _ = 2; > 114 END > 115 CASE(4) > 116 int parent_[] = {0,1,0,3,0,5,0,6,0,6,0,6,4,6,9,4,5,5,2,5,2}; > 117 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 118 int dist_[] = {93,42,104,105,59,73,161,130,30,81,62,93,131,133,139,5,13, > 119 vector <int> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); > 120 int maxDist = 162; > 121 int _ = 11; > 122 END > 123 /* > 124 CASE(5) > 125 int parent_[] = ; > 126 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 127 int dist_[] = ; > 128 vector <int> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); > 129 int maxDist = ; > 130 int _ = ; > 131 END > 132 CASE(6) > 133 int parent_[] = ; > 134 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 135 int dist_[] = ; > 136 vector <int> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); > 137 int maxDist = ; > 138 int _ = ; > 139 END > 140 */ > 141 } > 142 // END CUT HERE