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