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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 50 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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(*replies_)); 59 - int _ = 5; 60 -END 61 -CASE(1) 62 - int replies_[] = { 0 } 63 -; 64 - vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*replies_)); 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(*replies_)); 71 - int _ = 499; 72 -END 73 -CASE(3) 74 - int replies_[] = {1}; 75 - vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*replies_)); 76 - int _ = 2; 77 -END 78 -CASE(4) 79 - int replies_[] = {2}; 80 - vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*replies_)); 81 - int _ = 3; 82 -END 83 -CASE(5) 84 - int replies_[] = {1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}; 85 - vector <int> replies(replies_, replies_+sizeof(replies_)/sizeof(*replies_)); 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 59 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,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); G.resize(G.size()+1); } 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()), scc_id(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 component 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 scc !!!! not a good idea! 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 scc 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.end()) ); 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> after) 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 162 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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", "BAAAA" } 200 -; 201 - vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_)); 202 - string after_[] = { "AACCB", "DAAABC", "AAAAD", "ABCBA", "AABAAA", "AACAA" } 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 15 #include <cmath> 16 16 #include <cassert> 17 17 #include <cstring> 18 18 using namespace std; 19 19 typedef long long LL; 20 20 typedef complex<double> CMP; 21 21 22 -template<typename V> 23 -class Graph 22 +template<typename T> 23 +class IdGen 24 24 { 25 - map<V, int> v2id_; 26 - vector<V> id2v_; 25 + map<T, int> v2id_; 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 39 public: 40 + IdGen<Vert> idgen; 28 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); G.resize(G.size()+1); } 33 - return v2id_[t]; 46 + int s = idgen.v2id(s_); 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 54 G[s].push_back(t); 39 55 } 40 - const V& orig( int v ) 56 + 57 + void scc() 41 58 { 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()), scc_id(G.size()) 51 - { 52 - for(int v=0; v<G.size(); ++v) 59 + int N = G.size(); 60 + dfs_no.assign(N, 0); 61 + dfs_lo.assign(N, 0); 62 + pending = stack<int>(); 63 + scc_id.assign(N, -1); 64 + scc_list.clear(); 65 + scc_children.clear(); 66 + for(int v=0; v<N; ++v) 53 67 dfs(v); 54 68 } 55 69 56 - vector< vector<int> > scc; // scc[i] : the list of verts in the i-th component 57 - vector< vector<int> > forest; // the forest structure over sccs 70 + vector<int> scc_id; // which scc does the vert belong to? 71 + vector< vector<int> > scc_list; // list of nodes in the scc 72 + vector< vector<int> > scc_children; // forest relationship of sccs 58 73 59 74 private: 60 - const vector< vector<int> >& G; 61 75 int no; 62 - vector<int> dfs_no; // Special: 0 : not visited yet 63 - vector<int> dfs_lo; // Special: INT_MAX : already classified into some scc !!!! not a good idea! 64 - // rather use scc_id for that purpose (distinguishing assigned or not) 65 - vector<int> scc_id; 66 - vector<int> pending; 76 + vector<int> dfs_no; // 1-origin dfs-visit ID 77 + vector<int> dfs_lo; // the least ID in the vert's scc 78 + stack<int> pending; // current unclassigied verts 67 79 68 80 void dfs(int v) 69 81 { 82 + // visit v if not yet 70 83 if( dfs_no[v] ) 71 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 74 - for(int i=0; i<G[v].size(); ++i) // visit children 75 - { 88 + // visit children 89 + for(int i=0; i<G[v].size(); ++i) { 76 90 int u = G[v][i]; 77 91 dfs( u ); 78 - if( !is_already_classified_in_some_scc(u) ) 79 - dfs_lo[v] = min( dfs_lo[v], dfs_lo[G[v][i]] ); 92 + if( scc_id[u] == -1 ) 93 + dfs_lo[v] = min( dfs_lo[v], dfs_lo[u] ); 80 94 } 81 95 82 - pending.push_back(v); 83 - if( dfs_no[v] == dfs_lo[v] ) { // found the representative of a scc 84 - // todo: pending -> dfs_lo:=INT_MAX 85 - scc.push_back(pending), pending.clear(); 96 + // when v is the representative of scc 97 + if( dfs_no[v] == dfs_lo[v] ) { 98 + vector<int> scc; 99 + for(;;) { 100 + int w = pending.top(); pending.pop(); 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 107 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.end()) ); 108 + for(int j=0; j<scc.size(); ++j) 109 + for(int i=0; i<G[scc[j]].size(); ++i) 110 + children.insert( scc_id[G[scc[j]][i]] ); 111 + children.erase(scc_id[v]); 112 + scc_children.push_back( vector<int>(children.begin(), children.end()) ); 94 113 } 95 114 } 96 115 }; 97 - 98 116 99 117 class ImpossibleGame { public: 100 118 static LL C(LL n, LL k) { 101 119 LL v = 1; 102 120 for(int i=1; i<=k; ++i) 103 121 v = v * (n+1-i) / i; 104 122 return v; 105 123 } 124 + 106 125 static LL weight(LL a, LL b, LL c, LL d) { 107 126 return C(a+b+c+d,a) * C(b+c+d,b) * C(c+d,c); 108 127 } 109 128 110 129 long long getMinimum(int k, vector <string> before, vector <string> after) 111 130 { 112 131 vector< pair< vector<int>, vector<int> > > dif; ................................................................................ 114 133 { 115 134 vector<int> be(4), af(4); 116 135 for(int j=0; j<before[i].size(); ++j) be[before[i][j]-'A'] ++; 117 136 for(int j=0; j< after[i].size(); ++j) af[ after[i][j]-'A'] ++; 118 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 142 vector<int> v(4); 124 143 for(v[0]=0; v[0]<=k; ++v[0]) 125 144 for(v[1]=0; v[0]+v[1]<=k; ++v[1]) 126 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 { 129 - G.vert(v); 147 + v[3] = k - v[0] - v[1] - v[2]; 148 + G.addVert(v); 130 149 for(int i=0; i<dif.size(); ++i) 131 150 { 132 151 bool dame = false; 133 152 134 153 vector<int> u = v; 135 154 for(int k=0; k<4; ++k) 136 155 { 137 156 if( (u[k]-=dif[i].first[k]) < 0 ) 138 157 dame = true; 139 158 u[k] += dif[i].second[k]; 140 159 } 141 160 if( !dame ) 142 - G.edge(v, u); 161 + G.addEdge(v, u); 143 162 } 144 163 } 145 164 146 - StronglyConnectedComponent scc(G.G); 147 - return 0; 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)); 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 189 // BEGIN CUT HERE 152 190 #include <ctime> 153 191 double start_time; string timer() 154 192 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } ................................................................................ 162 200 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 163 201 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 164 202 #define END verify_case(_, ImpossibleGame().getMinimum(k, before, after));} 165 203 int main(){ 166 204 167 205 CASE(0) 168 206 int k = 1; 169 - string before_[] = { "A" } 170 -; 207 + string before_[] = { "A" }; 171 208 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_)); 172 - string after_[] = { "B" } 173 -; 209 + string after_[] = { "B" }; 174 210 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 175 211 long long _ = 2LL; 176 212 END 177 213 CASE(1) 178 214 int k = 2; 179 - string before_[] = { "A", "A", "D" } 180 -; 215 + string before_[] = { "A", "A", "D" }; 181 216 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_)); 182 - string after_[] = { "B", "C", "D" } 183 -; 217 + string after_[] = { "B", "C", "D" }; 184 218 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 185 219 long long _ = 5LL; 186 220 END 187 221 CASE(2) 188 222 int k = 2; 189 - string before_[] = { "B", "C", "D" } 190 -; 223 + string before_[] = { "B", "C", "D" }; 191 224 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_)); 192 - string after_[] = { "C", "D", "B" } 193 -; 225 + string after_[] = { "C", "D", "B" }; 194 226 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 195 227 long long _ = 9LL; 196 228 END 197 229 CASE(3) 198 230 int k = 6; 199 - string before_[] = { "AABBC", "AAAADA", "AAACA", "CABAA", "AAAAAA", "BAAAA" } 200 -; 231 + string before_[] = { "AABBC", "AAAADA", "AAACA", "CABAA", "AAAAAA", "BAAAA" }; 201 232 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_)); 202 - string after_[] = { "AACCB", "DAAABC", "AAAAD", "ABCBA", "AABAAA", "AACAA" } 203 -; 233 + string after_[] = { "AACCB", "DAAABC", "AAAAD", "ABCBA", "AABAAA", "AACAA" }; 204 234 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 205 235 long long _ = 499LL; 206 236 END 207 -/* 208 237 CASE(4) 209 - int k = ; 210 - string before_[] = ; 238 + int k = 7; 239 + string before_[] = {"BDBBB", "ACBBBBC", "BBBBC", "CCACCCB", "CC", "BBBBBBD", "BBDBBAB", "DBBCBB", "DBABABB", "BBBBABB", "BBBBB", "BBABB", "BBBBBDB", "ABDC", "BDBBDCB", "BBBBBAC", "BBBDBC", "BBBBBBA", "BBBBBBB", "BACCBB", "ABBDABB", "DC", "ABBDBB", "ACBCABB"}; 211 240 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_)); 212 - string after_[] = ; 241 + string after_[] = {"BADBC", "ACDBCBB", "BADCB", "BBBDBBC", "BD", "BBACCBD", "BBADBDB", "BBBBCC", "BBBCBBB", "BCBDCBD", "ABBBA", "DDBAB", "BCBDBDB", "BBCB", "BBCBBBB", "BABCBDB", "BBCCBD", "BBBBBCB", "DBCBADC", "BBBACA", "ABBABBC", "DB", "DBBCBB", "BBDBBBB"}; 213 242 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 214 - long long _ = LL; 243 + long long _ = 7112LL; 215 244 END 245 +/* 216 246 CASE(5) 217 247 int k = ; 218 248 string before_[] = ; 219 249 vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_)); 220 250 string after_[] = ; 221 251 vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 222 252 long long _ = LL; 223 253 END 224 254 */ 225 255 } 226 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(), children.end()) ); 102 + } 103 + } 104 +};