Overview
| SHA1 Hash: | b57cc94f1bd266969c70fdec1ad3afbe76a13fbb |
|---|---|
| Date: | 2011-10-08 15:42:58 |
| User: | kinaba |
| Comment: | Library for SCC added and verified. |
| 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
Deleted SRM/499-U/1A.cpp version [1b6c222f9c3582e7]
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 <cstring> < 18 using namespace std; < 19 typedef long long LL; < 20 typedef complex<double> CMP; < 21 < 22 class ColorfulRabbits { public: < 23 int getMinimum(vector <int> replies) < 24 { < 25 map<int,int> m; < 26 for(int i=0; i<replies.size(); ++i) < 27 m[replies[i]]++; < 28 int total = 0; < 29 for(map<int,int>::iterator it=m.begin(); it!=m.end(); ++it) < 30 { < 31 int s = it->first + 1; < 32 int n = it->second; < 33 total += (n+s-1) / s * s; < 34 } < 35 return total; < 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(_, ColorfulRabbits().getMinimum(replies));} < 53 int main(){ < 54 < 55 CASE(0) < 56 int replies_[] = { 1, 1, 2, 2 } < 57 ; < 58 vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*repli < 59 int _ = 5; < 60 END < 61 CASE(1) < 62 int replies_[] = { 0 } < 63 ; < 64 vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*repli < 65 int _ = 1; < 66 END < 67 CASE(2) < 68 int replies_[] = { 2, 2, 44, 2, 2, 2, 444, 2, 2 } < 69 ; < 70 vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*repli < 71 int _ = 499; < 72 END < 73 CASE(3) < 74 int replies_[] = {1}; < 75 vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*repli < 76 int _ = 2; < 77 END < 78 CASE(4) < 79 int replies_[] = {2}; < 80 vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*repli < 81 int _ = 3; < 82 END < 83 CASE(5) < 84 int replies_[] = {1000000,1000000,1000000,1000000,1000000,1000000,100000 < 85 vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*repli < 86 int _ = -1; < 87 END < 88 < 89 } < 90 // END CUT HERE <
Deleted SRM/499-U/1B-U.cpp version [13e543b5a0b1db44]
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 <cstring> < 18 using namespace std; < 19 typedef long long LL; < 20 typedef complex<double> CMP; < 21 < 22 class WhiteSpaceEditing { public: < 23 int getMinimum(vector <int> lines) < 24 { < 25 const int N = lines.size(); < 26 const int V = *max_element(lines.begin(), lines.end()); < 27 vector<int> dp(V+1), dp_neo(V+1); < 28 for(int v=0; v<=V; ++v) < 29 dp[v] = abs(v - lines[N-1]); < 30 for(int i=N-2; i>=0; --i) < 31 { < 32 int best = INT_MAX; < 33 for(int v=lines[i]; v>=0; --v) { < 34 best = min(best, dp[v]); < 35 dp_neo[v] = abs(v - lines[i]) + best; < 36 } < 37 best = INT_MAX; < 38 for(int v=lines[i]; v<=V; ++v) { < 39 best = min(best, dp[v]); < 40 dp_neo[v] = abs(v - lines[i]) + best; < 41 } < 42 dp.swap(dp_neo); < 43 } < 44 return dp[0] + N-1; < 45 } < 46 }; < 47 < 48 // BEGIN CUT HERE < 49 #include <ctime> < 50 double start_time; string timer() < 51 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) < 52 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) < 53 { os << "{ "; < 54 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) < 55 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return < 56 void verify_case(const int& Expected, const int& Received) { < 57 bool ok = (Expected == Received); < 58 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() < 59 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' < 60 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( < 61 #define END verify_case(_, WhiteSpaceEditing().getMinimum(lines));} < 62 int main(){ < 63 < 64 CASE(0) < 65 int lines_[] = { 3, 2, 3 }; < 66 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); < 67 int _ = 6; < 68 END < 69 CASE(1) < 70 int lines_[] = { 0 }; < 71 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); < 72 int _ = 0; < 73 END < 74 CASE(2) < 75 int lines_[] = { 1, 2, 4 } < 76 ; < 77 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); < 78 int _ = 6; < 79 END < 80 CASE(3) < 81 int lines_[] = { 250, 105, 155, 205, 350 } < 82 ; < 83 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); < 84 int _ = 499; < 85 END < 86 CASE(4) < 87 int lines_[] = {0}; < 88 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); < 89 int _ = 0; < 90 END < 91 CASE(5) < 92 int lines_[] = {1}; < 93 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); < 94 int _ = 1; < 95 END < 96 CASE(5) < 97 int lines_[] = {10}; < 98 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); < 99 int _ = 10; < 100 END < 101 CASE(5) < 102 int lines_[] = {10,10}; < 103 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); < 104 int _ = 11; < 105 END < 106 CASE(5) < 107 int lines_[] = {1000000,1000000,1000000,1000000,1000000,1000000,1000000, < 108 vector <int> lines(lines_, lines_+sizeof(lines_)/sizeof(*lines_)); < 109 int _ = 1000049; < 110 END < 111 < 112 } < 113 // END CUT HERE <
Deleted SRM/499-U/1C-U.cpp version [c23044dc81c5002a]
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 <cstring> < 18 using namespace std; < 19 typedef long long LL; < 20 typedef complex<double> CMP; < 21 < 22 template<typename V> < 23 class Graph < 24 { < 25 map<V, int> v2id_; < 26 vector<V> id2v_; < 27 public: < 28 vector< vector<int> > G; < 29 < 30 int vert( const V& t ) < 31 { < 32 if( !v2id_.count(t) ) { v2id_[t] = G.size(); id2v_.push_back(t); < 33 return v2id_[t]; < 34 } < 35 void edge( const V& s_, const V& t_ ) < 36 { < 37 int s=vert(s_), t=vert(t_); < 38 G[s].push_back(t); < 39 } < 40 const V& orig( int v ) < 41 { < 42 return id2v_[v]; < 43 } < 44 }; < 45 < 46 class StronglyConnectedComponent < 47 { < 48 public: < 49 StronglyConnectedComponent( const vector< vector<int> >& G ) < 50 : scc(), forest(), G(G), no(0), dfs_no(G.size()), dfs_lo(G.size( < 51 { < 52 for(int v=0; v<G.size(); ++v) < 53 dfs(v); < 54 } < 55 < 56 vector< vector<int> > scc; // scc[i] : the list of verts in the i-th < 57 vector< vector<int> > forest; // the forest structure over sccs < 58 < 59 private: < 60 const vector< vector<int> >& G; < 61 int no; < 62 vector<int> dfs_no; // Special: 0 : not visited yet < 63 vector<int> dfs_lo; // Special: INT_MAX : already classified into some s < 64 // rather use scc_id for that purpose (distinguishing assigned or not) < 65 vector<int> scc_id; < 66 vector<int> pending; < 67 < 68 void dfs(int v) < 69 { < 70 if( dfs_no[v] ) < 71 return; < 72 < 73 dfs_no[v] = dfs_lo[v] = ++no; // visit v < 74 for(int i=0; i<G[v].size(); ++i) // visit children < 75 { < 76 int u = G[v][i]; < 77 dfs( u ); < 78 if( !is_already_classified_in_some_scc(u) ) < 79 dfs_lo[v] = min( dfs_lo[v], dfs_lo[G[v][i]] ); < 80 } < 81 < 82 pending.push_back(v); < 83 if( dfs_no[v] == dfs_lo[v] ) { // found the representative of a < 84 // todo: pending -> dfs_lo:=INT_MAX < 85 scc.push_back(pending), pending.clear(); < 86 < 87 // construct scc-forest (if needed) < 88 scc_id[v] = scc.size()-1; < 89 set<int> children; < 90 for(int i=0; i<G[v].size(); ++i) < 91 if( dfs_lo[G[v][i]] != v ) < 92 children.insert( scc_id[dfs_lo[G[v][i]]] < 93 forest.push_back( vector<int>(children.begin(), children < 94 } < 95 } < 96 }; < 97 < 98 < 99 class ImpossibleGame { public: < 100 static LL C(LL n, LL k) { < 101 LL v = 1; < 102 for(int i=1; i<=k; ++i) < 103 v = v * (n+1-i) / i; < 104 return v; < 105 } < 106 static LL weight(LL a, LL b, LL c, LL d) { < 107 return C(a+b+c+d,a) * C(b+c+d,b) * C(c+d,c); < 108 } < 109 < 110 long long getMinimum(int k, vector <string> before, vector <string> afte < 111 { < 112 vector< pair< vector<int>, vector<int> > > dif; < 113 for(int i=0; i<after.size(); ++i) < 114 { < 115 vector<int> be(4), af(4); < 116 for(int j=0; j<before[i].size(); ++j) be[before[i][j]-'A < 117 for(int j=0; j< after[i].size(); ++j) af[ after[i][j]-'A < 118 dif.push_back( make_pair(be,af) ); < 119 } < 120 < 121 Graph< vector<int> > G; < 122 < 123 vector<int> v(4); < 124 for(v[0]=0; v[0]<=k; ++v[0]) < 125 for(v[1]=0; v[0]+v[1]<=k; ++v[1]) < 126 for(v[2]=0; v[0]+v[1]+v[2]<=k; ++v[2]) < 127 for(v[3]=0; v[0]+v[1]+v[2]+v[3]<=k; ++v[3]) < 128 { < 129 G.vert(v); < 130 for(int i=0; i<dif.size(); ++i) < 131 { < 132 bool dame = false; < 133 < 134 vector<int> u = v; < 135 for(int k=0; k<4; ++k) < 136 { < 137 if( (u[k]-=dif[i].first[k]) < 0 ) < 138 dame = true; < 139 u[k] += dif[i].second[k]; < 140 } < 141 if( !dame ) < 142 G.edge(v, u); < 143 } < 144 } < 145 < 146 StronglyConnectedComponent scc(G.G); < 147 return 0; < 148 } < 149 }; < 150 < 151 // BEGIN CUT HERE < 152 #include <ctime> < 153 double start_time; string timer() < 154 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) < 155 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) < 156 { os << "{ "; < 157 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) < 158 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return < 159 void verify_case(const long long& Expected, const long long& Received) { < 160 bool ok = (Expected == Received); < 161 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() < 162 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' < 163 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( < 164 #define END verify_case(_, ImpossibleGame().getMinimum(k, before, after));} < 165 int main(){ < 166 < 167 CASE(0) < 168 int k = 1; < 169 string before_[] = { "A" } < 170 ; < 171 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before < 172 string after_[] = { "B" } < 173 ; < 174 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); < 175 long long _ = 2LL; < 176 END < 177 CASE(1) < 178 int k = 2; < 179 string before_[] = { "A", "A", "D" } < 180 ; < 181 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before < 182 string after_[] = { "B", "C", "D" } < 183 ; < 184 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); < 185 long long _ = 5LL; < 186 END < 187 CASE(2) < 188 int k = 2; < 189 string before_[] = { "B", "C", "D" } < 190 ; < 191 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before < 192 string after_[] = { "C", "D", "B" } < 193 ; < 194 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); < 195 long long _ = 9LL; < 196 END < 197 CASE(3) < 198 int k = 6; < 199 string before_[] = { "AABBC", "AAAADA", "AAACA", "CABAA", "AAAAAA", "BAA < 200 ; < 201 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before < 202 string after_[] = { "AACCB", "DAAABC", "AAAAD", "ABCBA", "AABAAA", "AACA < 203 ; < 204 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); < 205 long long _ = 499LL; < 206 END < 207 /* < 208 CASE(4) < 209 int k = ; < 210 string before_[] = ; < 211 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before < 212 string after_[] = ; < 213 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); < 214 long long _ = LL; < 215 END < 216 CASE(5) < 217 int k = ; < 218 string before_[] = ; < 219 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before < 220 string after_[] = ; < 221 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); < 222 long long _ = LL; < 223 END < 224 */ < 225 } < 226 // END CUT HERE <
Name change from from SRM/499-U/1A.cpp to SRM/499/1A.cpp.
Name change from from SRM/499-U/1B-U.cpp to SRM/499/1B-U.cpp.
Modified SRM/499/1C.cpp from [c23044dc81c5002a] to [4983b441ed2ad4da].
15 #include <cmath> 15 #include <cmath> 16 #include <cassert> 16 #include <cassert> 17 #include <cstring> 17 #include <cstring> 18 using namespace std; 18 using namespace std; 19 typedef long long LL; 19 typedef long long LL; 20 typedef complex<double> CMP; 20 typedef complex<double> CMP; 21 21 22 template<typename V> | 22 template<typename T> 23 class Graph | 23 class IdGen 24 { 24 { 25 map<V, int> v2id_; | 25 map<T, int> v2id_; 26 vector<V> id2v_; | 26 vector<T> id2v_; > 27 public: > 28 int v2id(const T& v) { > 29 if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } > 30 return v2id_[v]; > 31 } > 32 const T& id2v(int i) const { return id2v_[i]; } > 33 int size() const { return id2v_.size(); } > 34 }; > 35 > 36 template<typename Vert> > 37 class SCC > 38 { 27 public: 39 public: > 40 IdGen<Vert> idgen; 28 vector< vector<int> > G; 41 vector< vector<int> > G; 29 42 30 int vert( const V& t ) | 43 public: > 44 void addVert( Vert s_ ) 31 { 45 { 32 if( !v2id_.count(t) ) { v2id_[t] = G.size(); id2v_.push_back(t); | 46 int s = idgen.v2id(s_); 33 return v2id_[t]; | 47 if( s >= G.size() ) G.resize(s+1); 34 } 48 } 35 void edge( const V& s_, const V& t_ ) < > 49 > 50 void addEdge( Vert s_, Vert t_ ) 36 { 51 { 37 int s=vert(s_), t=vert(t_); | 52 int s = idgen.v2id(s_), t = idgen.v2id(t_); > 53 if( max(s,t) >= G.size() ) G.resize(max(s,t)+1); 38 G[s].push_back(t); 54 G[s].push_back(t); 39 } 55 } 40 const V& orig( int v ) < > 56 > 57 void scc() 41 { 58 { 42 return id2v_[v]; | 59 int N = G.size(); 43 } < 44 }; < 45 < > 60 dfs_no.assign(N, 0); > 61 dfs_lo.assign(N, 0); > 62 pending = stack<int>(); 46 class StronglyConnectedComponent | 63 scc_id.assign(N, -1); 47 { < > 64 scc_list.clear(); 48 public: | 65 scc_children.clear(); 49 StronglyConnectedComponent( const vector< vector<int> >& G ) < 50 : scc(), forest(), G(G), no(0), dfs_no(G.size()), dfs_lo(G.size( < 51 { < 52 for(int v=0; v<G.size(); ++v) | 66 for(int v=0; v<N; ++v) 53 dfs(v); 67 dfs(v); 54 } 68 } 55 69 > 70 vector<int> scc_id; // which scc does the vert belong to? 56 vector< vector<int> > scc; // scc[i] : the list of verts in the i-th | 71 vector< vector<int> > scc_list; // list of nodes in the scc 57 vector< vector<int> > forest; // the forest structure over sccs | 72 vector< vector<int> > scc_children; // forest relationship of sccs 58 73 59 private: 74 private: 60 const vector< vector<int> >& G; < 61 int no; 75 int no; 62 vector<int> dfs_no; // Special: 0 : not visited yet | 76 vector<int> dfs_no; // 1-origin dfs-visit ID 63 vector<int> dfs_lo; // Special: INT_MAX : already classified into some s | 77 vector<int> dfs_lo; // the least ID in the vert's scc 64 // rather use scc_id for that purpose (distinguishing assigned or not) < 65 vector<int> scc_id; < 66 vector<int> pending; | 78 stack<int> pending; // current unclassigied verts 67 79 68 void dfs(int v) 80 void dfs(int v) 69 { 81 { > 82 // visit v if not yet 70 if( dfs_no[v] ) 83 if( dfs_no[v] ) 71 return; 84 return; > 85 dfs_no[v] = dfs_lo[v] = ++no; > 86 pending.push(v); 72 87 73 dfs_no[v] = dfs_lo[v] = ++no; // visit v | 88 // visit children 74 for(int i=0; i<G[v].size(); ++i) // visit children | 89 for(int i=0; i<G[v].size(); ++i) { 75 { < 76 int u = G[v][i]; 90 int u = G[v][i]; 77 dfs( u ); 91 dfs( u ); 78 if( !is_already_classified_in_some_scc(u) ) | 92 if( scc_id[u] == -1 ) 79 dfs_lo[v] = min( dfs_lo[v], dfs_lo[G[v][i]] ); | 93 dfs_lo[v] = min( dfs_lo[v], dfs_lo[u] ); 80 } 94 } 81 95 82 pending.push_back(v); | 96 // when v is the representative of scc 83 if( dfs_no[v] == dfs_lo[v] ) { // found the representative of a | 97 if( dfs_no[v] == dfs_lo[v] ) { 84 // todo: pending -> dfs_lo:=INT_MAX | 98 vector<int> scc; > 99 for(;;) { > 100 int w = pending.top(); pending.pop(); 85 scc.push_back(pending), pending.clear(); | 101 scc.push_back(w); > 102 scc_id[w] = scc_list.size(); > 103 if( w == v ) break; > 104 } > 105 scc_list.push_back(scc); 86 106 87 // construct scc-forest (if needed) < 88 scc_id[v] = scc.size()-1; < 89 set<int> children; 107 set<int> children; > 108 for(int j=0; j<scc.size(); ++j) 90 for(int i=0; i<G[v].size(); ++i) | 109 for(int i=0; i<G[scc[j]].size(); ++i) 91 if( dfs_lo[G[v][i]] != v ) < 92 children.insert( scc_id[dfs_lo[G[v][i]]] | 110 children.insert( scc_id[G[scc[j]][i]] ); > 111 children.erase(scc_id[v]); 93 forest.push_back( vector<int>(children.begin(), children | 112 scc_children.push_back( vector<int>(children.begin(), ch 94 } 113 } 95 } 114 } 96 }; 115 }; 97 < 98 116 99 class ImpossibleGame { public: 117 class ImpossibleGame { public: 100 static LL C(LL n, LL k) { 118 static LL C(LL n, LL k) { 101 LL v = 1; 119 LL v = 1; 102 for(int i=1; i<=k; ++i) 120 for(int i=1; i<=k; ++i) 103 v = v * (n+1-i) / i; 121 v = v * (n+1-i) / i; 104 return v; 122 return v; 105 } 123 } > 124 106 static LL weight(LL a, LL b, LL c, LL d) { 125 static LL weight(LL a, LL b, LL c, LL d) { 107 return C(a+b+c+d,a) * C(b+c+d,b) * C(c+d,c); 126 return C(a+b+c+d,a) * C(b+c+d,b) * C(c+d,c); 108 } 127 } 109 128 110 long long getMinimum(int k, vector <string> before, vector <string> afte 129 long long getMinimum(int k, vector <string> before, vector <string> afte 111 { 130 { 112 vector< pair< vector<int>, vector<int> > > dif; 131 vector< pair< vector<int>, vector<int> > > dif; ................................................................................................................................................................................ 114 { 133 { 115 vector<int> be(4), af(4); 134 vector<int> be(4), af(4); 116 for(int j=0; j<before[i].size(); ++j) be[before[i][j]-'A 135 for(int j=0; j<before[i].size(); ++j) be[before[i][j]-'A 117 for(int j=0; j< after[i].size(); ++j) af[ after[i][j]-'A 136 for(int j=0; j< after[i].size(); ++j) af[ after[i][j]-'A 118 dif.push_back( make_pair(be,af) ); 137 dif.push_back( make_pair(be,af) ); 119 } 138 } 120 139 121 Graph< vector<int> > G; | 140 SCC< vector<int> > G; 122 141 123 vector<int> v(4); 142 vector<int> v(4); 124 for(v[0]=0; v[0]<=k; ++v[0]) 143 for(v[0]=0; v[0]<=k; ++v[0]) 125 for(v[1]=0; v[0]+v[1]<=k; ++v[1]) 144 for(v[1]=0; v[0]+v[1]<=k; ++v[1]) 126 for(v[2]=0; v[0]+v[1]+v[2]<=k; ++v[2]) 145 for(v[2]=0; v[0]+v[1]+v[2]<=k; ++v[2]) 127 for(v[3]=0; v[0]+v[1]+v[2]+v[3]<=k; ++v[3]) < 128 { 146 { > 147 v[3] = k - v[0] - v[1] - v[2]; 129 G.vert(v); | 148 G.addVert(v); 130 for(int i=0; i<dif.size(); ++i) 149 for(int i=0; i<dif.size(); ++i) 131 { 150 { 132 bool dame = false; 151 bool dame = false; 133 152 134 vector<int> u = v; 153 vector<int> u = v; 135 for(int k=0; k<4; ++k) 154 for(int k=0; k<4; ++k) 136 { 155 { 137 if( (u[k]-=dif[i].first[k]) < 0 ) 156 if( (u[k]-=dif[i].first[k]) < 0 ) 138 dame = true; 157 dame = true; 139 u[k] += dif[i].second[k]; 158 u[k] += dif[i].second[k]; 140 } 159 } 141 if( !dame ) 160 if( !dame ) 142 G.edge(v, u); | 161 G.addEdge(v, u); 143 } 162 } 144 } 163 } 145 164 146 StronglyConnectedComponent scc(G.G); | 165 G.scc(); > 166 > 167 LL ans = 0; > 168 for(int v=0; v<G.scc_list.size(); ++v) > 169 ans = max(ans, rec(v, G)); 147 return 0; | 170 return ans; > 171 } > 172 > 173 map<int, LL> memo; > 174 LL rec(int v, SCC< vector<int> >& G) > 175 { > 176 if( memo.count(v) ) > 177 return memo[v]; > 178 LL mx = 0; > 179 for(int i=0; i<G.scc_children[v].size(); ++i) > 180 mx = max(mx, rec(G.scc_children[v][i], G)); > 181 for(int i=0; i<G.scc_list[v].size(); ++i) { > 182 const vector<int>& str = G.idgen.id2v(G.scc_list[v][i]); > 183 mx += weight(str[0], str[1], str[2], str[3]); > 184 } > 185 return memo[v] = mx; 148 } 186 } 149 }; 187 }; 150 188 151 // BEGIN CUT HERE 189 // BEGIN CUT HERE 152 #include <ctime> 190 #include <ctime> 153 double start_time; string timer() 191 double start_time; string timer() 154 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) 192 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) ................................................................................................................................................................................ 162 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' 200 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' 163 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( 201 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( 164 #define END verify_case(_, ImpossibleGame().getMinimum(k, before, after));} 202 #define END verify_case(_, ImpossibleGame().getMinimum(k, before, after));} 165 int main(){ 203 int main(){ 166 204 167 CASE(0) 205 CASE(0) 168 int k = 1; 206 int k = 1; 169 string before_[] = { "A" } | 207 string before_[] = { "A" }; 170 ; < 171 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before 208 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before 172 string after_[] = { "B" } | 209 string after_[] = { "B" }; 173 ; < 174 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 210 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 175 long long _ = 2LL; 211 long long _ = 2LL; 176 END 212 END 177 CASE(1) 213 CASE(1) 178 int k = 2; 214 int k = 2; 179 string before_[] = { "A", "A", "D" } | 215 string before_[] = { "A", "A", "D" }; 180 ; < 181 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before 216 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before 182 string after_[] = { "B", "C", "D" } | 217 string after_[] = { "B", "C", "D" }; 183 ; < 184 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 218 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 185 long long _ = 5LL; 219 long long _ = 5LL; 186 END 220 END 187 CASE(2) 221 CASE(2) 188 int k = 2; 222 int k = 2; 189 string before_[] = { "B", "C", "D" } | 223 string before_[] = { "B", "C", "D" }; 190 ; < 191 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before 224 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before 192 string after_[] = { "C", "D", "B" } | 225 string after_[] = { "C", "D", "B" }; 193 ; < 194 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 226 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 195 long long _ = 9LL; 227 long long _ = 9LL; 196 END 228 END 197 CASE(3) 229 CASE(3) 198 int k = 6; 230 int k = 6; 199 string before_[] = { "AABBC", "AAAADA", "AAACA", "CABAA", "AAAAAA", "BAA | 231 string before_[] = { "AABBC", "AAAADA", "AAACA", "CABAA", "AAAAAA", "BAA 200 ; < 201 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before 232 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before 202 string after_[] = { "AACCB", "DAAABC", "AAAAD", "ABCBA", "AABAAA", "AACA | 233 string after_[] = { "AACCB", "DAAABC", "AAAAD", "ABCBA", "AABAAA", "AACA 203 ; < 204 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 234 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 205 long long _ = 499LL; 235 long long _ = 499LL; 206 END 236 END 207 /* < 208 CASE(4) 237 CASE(4) 209 int k = ; | 238 int k = 7; 210 string before_[] = ; | 239 string before_[] = {"BDBBB", "ACBBBBC", "BBBBC", "CCACCCB", "CC", "BBBBB 211 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before 240 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before 212 string after_[] = ; | 241 string after_[] = {"BADBC", "ACDBCBB", "BADCB", "BBBDBBC", "BD", "BBACCB 213 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 242 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 214 long long _ = LL; | 243 long long _ = 7112LL; 215 END 244 END > 245 /* 216 CASE(5) 246 CASE(5) 217 int k = ; 247 int k = ; 218 string before_[] = ; 248 string before_[] = ; 219 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before 249 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before 220 string after_[] = ; 250 string after_[] = ; 221 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 251 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 222 long long _ = LL; 252 long long _ = LL; 223 END 253 END 224 */ 254 */ 225 } 255 } 226 // END CUT HERE 256 // END CUT HERE
Added lib/graph/scc.cpp version [1f3d1cfa1b9a8b8a]
> 1 > 2 //------------------------------------------------------------- > 3 // Strongly Connected Component of a Directed Graph > 4 // O(E) > 5 // > 6 // Verified by > 7 // - SRM 499 Div1 LV3 > 8 // > 9 // Using "Spagetthi Source"'s one path algorithm > 10 //------------------------------------------------------------- > 11 > 12 template<typename T> > 13 class IdGen > 14 { > 15 map<T, int> v2id_; > 16 vector<T> id2v_; > 17 public: > 18 int v2id(const T& v) { > 19 if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } > 20 return v2id_[v]; > 21 } > 22 const T& id2v(int i) const { return id2v_[i]; } > 23 int size() const { return id2v_.size(); } > 24 }; > 25 > 26 template<typename Vert> > 27 class SCC > 28 { > 29 IdGen<Vert> idgen; > 30 vector< vector<int> > G; > 31 > 32 public: > 33 void addVert( Vert s_ ) > 34 { > 35 int s = idgen.v2id(s_); > 36 if( s >= G.size() ) G.resize(s+1); > 37 } > 38 > 39 void addEdge( Vert s_, Vert t_ ) > 40 { > 41 int s = idgen.v2id(s_), t = idgen.v2id(t_); > 42 if( max(s,t) >= G.size() ) G.resize(max(s,t)+1); > 43 G[s].push_back(t); > 44 } > 45 > 46 void scc() > 47 { > 48 int N = G.size(); > 49 dfs_no.assign(N, 0); > 50 dfs_lo.assign(N, 0); > 51 pending = stack<int>(); > 52 scc_id.assign(N, -1); > 53 scc_list.clear(); > 54 scc_children.clear(); > 55 for(int v=0; v<N; ++v) > 56 dfs(v); > 57 } > 58 > 59 vector<int> scc_id; // which scc does the vert belong to? > 60 vector< vector<int> > scc_list; // list of nodes in the scc > 61 vector< vector<int> > scc_children; // forest relationship of sccs > 62 > 63 private: > 64 int no; > 65 vector<int> dfs_no; // 1-origin dfs-visit ID > 66 vector<int> dfs_lo; // the least ID in the vert's scc > 67 stack<int> pending; // current unclassigied verts > 68 > 69 void dfs(int v) > 70 { > 71 // visit v if not yet > 72 if( dfs_no[v] ) > 73 return; > 74 dfs_no[v] = dfs_lo[v] = ++no; > 75 pending.push(v); > 76 > 77 // visit children > 78 for(int i=0; i<G[v].size(); ++i) { > 79 int u = G[v][i]; > 80 dfs( u ); > 81 if( scc_id[u] == -1 ) > 82 dfs_lo[v] = min( dfs_lo[v], dfs_lo[u] ); > 83 } > 84 > 85 // when v is the representative of scc > 86 if( dfs_no[v] == dfs_lo[v] ) { > 87 vector<int> scc; > 88 for(;;) { > 89 int w = pending.top(); pending.pop(); > 90 scc.push_back(w); > 91 scc_id[w] = scc_list.size(); > 92 if( w == v ) break; > 93 } > 94 scc_list.push_back(scc); > 95 > 96 set<int> children; > 97 for(int j=0; j<scc.size(); ++j) > 98 for(int i=0; i<G[scc[j]].size(); ++i) > 99 children.insert( scc_id[G[scc[j]][i]] ); > 100 children.erase(scc_id[v]); > 101 scc_children.push_back( vector<int>(children.begin(), ch > 102 } > 103 } > 104 };