Differences From Artifact [c23044dc81c5002a]:
- File
SRM/499-U/1C-U.cpp
- 2011-03-20 00:13:20 - part of checkin [2de557d8c0] on branch trunk - 499 (user: kinaba) [annotate]
To Artifact [4983b441ed2ad4da]:
- File
SRM/499/1C.cpp
- 2011-10-08 15:42:58 - part of checkin [b57cc94f1b] on branch trunk - Library for SCC added and verified. (user: kinaba) [annotate]
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