4fd800b3a8 2011-02-23 kinaba: #include <iostream> 4fd800b3a8 2011-02-23 kinaba: #include <sstream> 4fd800b3a8 2011-02-23 kinaba: #include <iomanip> 4fd800b3a8 2011-02-23 kinaba: #include <vector> 4fd800b3a8 2011-02-23 kinaba: #include <string> 4fd800b3a8 2011-02-23 kinaba: #include <map> 4fd800b3a8 2011-02-23 kinaba: #include <set> 4fd800b3a8 2011-02-23 kinaba: #include <algorithm> 4fd800b3a8 2011-02-23 kinaba: #include <numeric> 4fd800b3a8 2011-02-23 kinaba: #include <iterator> 4fd800b3a8 2011-02-23 kinaba: #include <functional> 4fd800b3a8 2011-02-23 kinaba: #include <complex> 4fd800b3a8 2011-02-23 kinaba: #include <queue> 4fd800b3a8 2011-02-23 kinaba: #include <stack> 4fd800b3a8 2011-02-23 kinaba: #include <cmath> 4fd800b3a8 2011-02-23 kinaba: #include <cassert> 4fd800b3a8 2011-02-23 kinaba: #include <cstring> 4fd800b3a8 2011-02-23 kinaba: using namespace std; 4fd800b3a8 2011-02-23 kinaba: typedef long long LL; 4fd800b3a8 2011-02-23 kinaba: typedef complex<double> CMP; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: typedef int vert; 4fd800b3a8 2011-02-23 kinaba: typedef vert edge; 4fd800b3a8 2011-02-23 kinaba: typedef vector<edge> edges; 4fd800b3a8 2011-02-23 kinaba: typedef vector<edges> graph; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<G[v].size(); ++i) { 4fd800b3a8 2011-02-23 kinaba: vert u = G[v][i]; 4fd800b3a8 2011-02-23 kinaba: if( visited[u] ) continue; 4fd800b3a8 2011-02-23 kinaba: visited[u] = true; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) ) 4fd800b3a8 2011-02-23 kinaba: { matchTo[v]=u, matchTo[u]=v; return true; } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return false; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: template<int NV> 4fd800b3a8 2011-02-23 kinaba: int biMatch( graph& G, int L ) // [0,L):left, [L,?):right 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: vector<vert> matchTo(G.size(), -1); 4fd800b3a8 2011-02-23 kinaba: int ans = 0; 4fd800b3a8 2011-02-23 kinaba: for(vert v=0; v<L; ++v) { 4fd800b3a8 2011-02-23 kinaba: bool visited[NV] = {}; 4fd800b3a8 2011-02-23 kinaba: if( augment(G, v, matchTo, visited) ) 4fd800b3a8 2011-02-23 kinaba: ++ans; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return ans; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: int bitcnt(LL x) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int c = 0; 4fd800b3a8 2011-02-23 kinaba: for(; x; x>>=1) 4fd800b3a8 2011-02-23 kinaba: c += x&1; 4fd800b3a8 2011-02-23 kinaba: return c; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: class MallSecurity { public: 4fd800b3a8 2011-02-23 kinaba: pair<graph, int> generateBipartiteGraph( 4fd800b3a8 2011-02-23 kinaba: const vector<int>& As, const vector<int>& Bs, const vector<int>& Cs, const vector<int>& Ds, 4fd800b3a8 2011-02-23 kinaba: const vector<int>& Ks, int msf, int mask ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: // construct a bipartite graph representation, in which 4fd800b3a8 2011-02-23 kinaba: // - "even"-floor stations go to the left 4fd800b3a8 2011-02-23 kinaba: // - "odd"-floor stations go to the right 4fd800b3a8 2011-02-23 kinaba: // here floor number is normalized by rotating the msf-th floor to zero 4fd800b3a8 2011-02-23 kinaba: #define LR(f) (((f)>msf ? (f)-msf : Ks.size()-msf+(f))%2) 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // assign interger-ID for each "choosable" station, i.e., 4fd800b3a8 2011-02-23 kinaba: // a station which is not at msf and is not connected to a 'mask'ed station on msf 4fd800b3a8 2011-02-23 kinaba: map<pair<int,int>,int> ID; 4fd800b3a8 2011-02-23 kinaba: int nextID[2] = {0,0}; // use different sets of IDs for even/odd floors 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: for(int f=0; f<Ks.size(); ++f) if( f != msf ) 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<Ks[f]; ++i) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: bool can_use = true; 4fd800b3a8 2011-02-23 kinaba: for(int j=0; j<As.size(); ++j) 4fd800b3a8 2011-02-23 kinaba: if( Cs[j]==f && As[j]==i && Ds[j]==msf && (mask & 1<<Bs[j]) 4fd800b3a8 2011-02-23 kinaba: || Ds[j]==f && Bs[j]==i && Cs[j]==msf && (mask & 1<<As[j]) ) 4fd800b3a8 2011-02-23 kinaba: can_use = false; 4fd800b3a8 2011-02-23 kinaba: if( can_use ) 4fd800b3a8 2011-02-23 kinaba: ID[make_pair(f,i)] = nextID[LR(f)]++; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // then create the graph 4fd800b3a8 2011-02-23 kinaba: graph G( nextID[0] + nextID[1] ); 4fd800b3a8 2011-02-23 kinaba: for(int j=0; j<As.size(); ++j) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: pair<int,int> p(Cs[j], As[j]); 4fd800b3a8 2011-02-23 kinaba: pair<int,int> q(Ds[j], Bs[j]); 4fd800b3a8 2011-02-23 kinaba: if( ID.count(p) && ID.count(q) ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int pid = ID[p] + (LR(Cs[j]) ? nextID[0] : 0); 4fd800b3a8 2011-02-23 kinaba: int qid = ID[q] + (LR(Ds[j]) ? nextID[0] : 0); 4fd800b3a8 2011-02-23 kinaba: G[pid].push_back(qid); 4fd800b3a8 2011-02-23 kinaba: G[qid].push_back(pid); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return make_pair(G, nextID[0]); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: int maxGuards(int N, vector <string> escDescription) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: // parse the input 4fd800b3a8 2011-02-23 kinaba: vector<int> As, Bs, Cs, Ds, Ks(N); 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: stringstream sin; 4fd800b3a8 2011-02-23 kinaba: copy( escDescription.begin(), escDescription.end(), ostream_iterator<string>(sin,"") ); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: for(int A,B,C; sin>>A>>B>>C; ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: {char comma; sin>>comma;} 4fd800b3a8 2011-02-23 kinaba: --A, --B, --C; int D=(C+1)%N; // to 0-orign 4fd800b3a8 2011-02-23 kinaba: As.push_back(A); 4fd800b3a8 2011-02-23 kinaba: Bs.push_back(B); 4fd800b3a8 2011-02-23 kinaba: Cs.push_back(C); 4fd800b3a8 2011-02-23 kinaba: Ds.push_back(D); 4fd800b3a8 2011-02-23 kinaba: Ks[C] = max(Ks[C], A+1); 4fd800b3a8 2011-02-23 kinaba: Ks[D] = max(Ks[D], B+1); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // the most simple floor, where the number Ks[msf] of stations is the least 4fd800b3a8 2011-02-23 kinaba: int msf = min_element(Ks.begin(), Ks.end()) - Ks.begin(); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // try all possibilities at the msf-th floor 4fd800b3a8 2011-02-23 kinaba: size_t answer = 0; 4fd800b3a8 2011-02-23 kinaba: for(int mask=0; mask<(1<<Ks[msf]); ++mask) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: // then the rest of the part becomes a bipartite graph 4fd800b3a8 2011-02-23 kinaba: pair<graph, int> G = generateBipartiteGraph(As,Bs,Cs,Ds,Ks,msf,mask); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // |MaxIndenepdentSet| == |V|-|MinCover| =(for bipartite graphs)= |V|-|MaxMatch| 4fd800b3a8 2011-02-23 kinaba: answer = max(answer, G.first.size() - biMatch<100>(G.first,G.second) + bitcnt(mask)); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return answer; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // BEGIN CUT HERE 4fd800b3a8 2011-02-23 kinaba: #include <ctime> 4fd800b3a8 2011-02-23 kinaba: double start_time; string timer() 4fd800b3a8 2011-02-23 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 4fd800b3a8 2011-02-23 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 4fd800b3a8 2011-02-23 kinaba: { os << "{ "; 4fd800b3a8 2011-02-23 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 4fd800b3a8 2011-02-23 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 4fd800b3a8 2011-02-23 kinaba: void verify_case(const int& Expected, const int& Received) { 4fd800b3a8 2011-02-23 kinaba: bool ok = (Expected == Received); 4fd800b3a8 2011-02-23 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 4fd800b3a8 2011-02-23 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 4fd800b3a8 2011-02-23 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 4fd800b3a8 2011-02-23 kinaba: #define END verify_case(_, MallSecurity().maxGuards(N, escDescription));} 4fd800b3a8 2011-02-23 kinaba: int main(){ 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: CASE(0) 4fd800b3a8 2011-02-23 kinaba: int N = 10; 4fd800b3a8 2011-02-23 kinaba: string escDescription_[] = {"1 1 1,1 1 2,1 1 3,1 1 4,1 1 5,1 1 6,1 1 7,1 1 8,1 ", 4fd800b3a8 2011-02-23 kinaba: "1 9,1 1 10"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> escDescription(escDescription_, escDescription_+sizeof(escDescription_)/sizeof(*escDescription_)); 4fd800b3a8 2011-02-23 kinaba: int _ = 5; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(1) 4fd800b3a8 2011-02-23 kinaba: int N = 11; 4fd800b3a8 2011-02-23 kinaba: string escDescription_[] = {"1 1 1,1 1 2,1 1 3,1 1 4,1 1 5,1 1 6,1 1 7,1 1 8,1 ", 4fd800b3a8 2011-02-23 kinaba: "1 9,1 1 10"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> escDescription(escDescription_, escDescription_+sizeof(escDescription_)/sizeof(*escDescription_)); 4fd800b3a8 2011-02-23 kinaba: int _ = 6; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(2) 4fd800b3a8 2011-02-23 kinaba: int N = 10; 4fd800b3a8 2011-02-23 kinaba: string escDescription_[] = {"1 1 7,1 2 9,2 1", 4fd800b3a8 2011-02-23 kinaba: " 8,1 2 6,1 1 8,1 2 3,1 2 2,2 ", 4fd800b3a8 2011-02-23 kinaba: "2 4,1 1 1,2 1 2,3 2 3,1 1 5,2 1 1,4 ", 4fd800b3a8 2011-02-23 kinaba: "1 7,1 1 10,3 2 5,1 2 5,3 3 1,", 4fd800b3a8 2011-02-23 kinaba: "3 2 8,3 1 2,1 1 3,4 4 2,2", 4fd800b3a8 2011-02-23 kinaba: " 4 6,4 2 5,2 3 3,6 4 1,5 2 8,1 3 6,1 3 7,", 4fd800b3a8 2011-02-23 kinaba: "4 3 8,1 3 8,5 2 3,4 2 8,2 6 7,1 3 9,", 4fd800b3a8 2011-02-23 kinaba: "1 1 4,6 1 1,2 3 1,5 1 5,6 1 8,5 ", 4fd800b3a8 2011-02-23 kinaba: "2 2,3 2 10,3 3 9,1 5 2,4 1 1,1 5 10"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> escDescription(escDescription_, escDescription_+sizeof(escDescription_)/sizeof(*escDescription_)); 4fd800b3a8 2011-02-23 kinaba: int _ = 25; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(3) 4fd800b3a8 2011-02-23 kinaba: int N = 13; 4fd800b3a8 2011-02-23 kinaba: string escDescription_[] = {"5 1 11,2 3 9,3 7 10,5 2 11,5 5 8,7 5 6,5 2 13,4 2 ", "8,3 7 12,7 3 9,2 7 12,8 5 4,4 6 6,7 3 11,1 5 7,4 4", " 10,3 1 9,7 2 5,4 6 12,5 5 5,6 6 5,1 5 12,6 4 3,2 ", "5 1,2 5 5,5 4 3,5 6 8,3 5 11,6 2 7,8 3 7,6 8 2,5 3", " 12,6 1 3,6 2 8,6 2 6,5 5 6,3 2 2,4 3 11,1 8 2,3 4", " 5,1 6 8,5 7 6,3 2 7,4 1 9,4 7 8,4 3 7,4 5 4,2 1 7", ",5 4 2,6 5 4,6 8 13,2 6 3,6 3 6,3 4 7,4 5 8,1 3 11", ",6 6 1,5 1 8,3 5 7,7 3 4,3 4 13,5 4 6,7 4 1,3 1 13", ",1 5 6,7 7 12,4 7 3,7 4 4,1 6 10,3 4 6,7 4 10,5 3 ", "13,1 1 4,8 7 7,2 7 13,5 6 11,1 4 9,4 4 13,2 6 8,7 ", "5 10,1 2 7,1 7 8,8 8 3,2 4 1,7 6 12,2 5 12,2 2 3,1", " 2 2,1 4 7,4 1 11,6 2 4,4 6 4,6 3 8,5 6 7,4 2 4,2 ", "7 6,7 2 1,3 4 4,4 4 3,1 2 3,1 1 10,2 3 8,6 6 11,5 ", "5 13,7 7 4,5 3 11,6 6 8,6 4 12,6 1 7,3 8 9,2 1 1,5", " 5 10,8 1 7,7 2 6,1 7 4,5 1 12,2 5 7,6 7 7,3 6 3,8", " 1 1,3 8 2,3 6 6,3 6 4,6 3 2,4 5 5,2 6 4,3 2 6,7 6", " 5,1 8 6,5 5 4,2 7 10", ",1 7 9,1 1 3,4 4 4,4 3 5,4 2 10,5 7 3,5 3 5,3 6 9,", "2 5 11,3 2 3,4 1 1,2 5 10,5 1 4,6 5 5,1 7 5,7 5 5,", "8 5 12,7 8 13,1 2 10,3 7 6,4 7 13,4 3 13,6 4 11,6 ", "7 4,2 6 7,2 7 3,7 8 8,6 1 12,6 7 8,3 1 10,8 6 1,1 ", "7 10,1 3 9,7 7 11,5 6 4,7 7 1,4 2 1,8 2 3,7 8 2,1 ", "4 13,2 3 13,3 2 11,6 7 12,4 8 2,5 6 1,6 3 12,3 5 3", ",1 5 10,1 4 5,4 6 10,1 6 6,6 3 5,4 3 12,6 2 11,3 8", " 3,7 5 3,6 7 10,3 2 13,7 4 3,1 7 12,2 7 4,4 7 1,8 ", "5 10,6 6 4,6 7 2,4 7 7,1 3 1,1 4 12,6 5 7,5 1 13,5", " 8 13,2 1 10,5 2 7,8 3 10,5 1 5,1 4 6,1 1 6,5 2 2,", "2 3 11,3 2 10,2 1 13,8 2 9,3 5 2,1 7 2,3 3 5,5 2 5", ",8 4 12,7 3 2,2 5 3,3 7 1,6 7 6,8 5 9,4 5 7,2 8 3,", "2 4 6,7 1 10,5 8 11,4 7 6,7 6 4,3 6 11,5 3 1,7 7 8", ",1 6 9,7 6 7,1 2 1,2 2 12,3 5 9,4 4 1,6 4 5,5 8 3,", "2 1 2,6 6 10,1 5 9,8 1 3,5 1 10,4 7 2,8 4 9,2 2 7,", "2 3 4,6 1 4,1 4 11,7 1 1,3 7 7,5 4 13,1 6 1,4 7 12"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> escDescription(escDescription_, escDescription_+sizeof(escDescription_)/sizeof(*escDescription_)); 4fd800b3a8 2011-02-23 kinaba: int _ = 50; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: /* 4fd800b3a8 2011-02-23 kinaba: CASE(4) 4fd800b3a8 2011-02-23 kinaba: int N = ; 4fd800b3a8 2011-02-23 kinaba: string escDescription_[] = ; 4fd800b3a8 2011-02-23 kinaba: vector <string> escDescription(escDescription_, escDescription_+sizeof(escDescription_)/sizeof(*escDescription_)); 4fd800b3a8 2011-02-23 kinaba: int _ = ; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: */ 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE