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