Artifact Content
Not logged in

Artifact ef7e420ef333d5ce8ca0790a7125caf70d7adfc1


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

typedef int           vert;
typedef vert          edge;
typedef vector<edge>  edges;
typedef vector<edges> graph;

bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] )
{
	for(int i=0; i<G[v].size(); ++i) {
		vert u = G[v][i];
		if( visited[u] ) continue;
		visited[u] = true;

		if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) )
			{ matchTo[v]=u, matchTo[u]=v; return true; }
	}
	return false;
}

template<int NV>
int biMatch( graph& G, int L ) // [0,L):left, [L,?):right
{
	vector<vert> matchTo(G.size(), -1);
	int ans = 0;
	for(vert v=0; v<L; ++v) {
		bool visited[NV] = {};
		if( augment(G, v, matchTo, visited) )
			++ans;
	}
	return ans;
}

int bitcnt(LL x)
{
	int c = 0;
	for(; x; x>>=1)
		c += x&1;
	return c;
}

class MallSecurity { public:
	pair<graph, int> generateBipartiteGraph(
		const vector<int>& As, const vector<int>& Bs, const vector<int>& Cs, const vector<int>& Ds,
		const vector<int>& Ks, int msf, int mask )
	{
		// construct a bipartite graph representation, in which
		//   - "even"-floor stations go to the left
		//   - "odd"-floor stations go to the right
		// here floor number is normalized by rotating the msf-th floor to zero
		#define LR(f) (((f)>msf ? (f)-msf : Ks.size()-msf+(f))%2)

		// assign interger-ID for each "choosable" station, i.e.,
		// a station which is not at msf and is not connected to a 'mask'ed station on msf
		map<pair<int,int>,int> ID;
		int nextID[2] = {0,0}; // use different sets of IDs for even/odd floors
		{
			for(int f=0; f<Ks.size(); ++f) if( f != msf )
			for(int i=0; i<Ks[f]; ++i)
			{
				bool can_use = true;
				for(int j=0; j<As.size(); ++j)
					if( Cs[j]==f && As[j]==i && Ds[j]==msf && (mask & 1<<Bs[j])
					 || Ds[j]==f && Bs[j]==i && Cs[j]==msf && (mask & 1<<As[j]) )
					 can_use = false;
				if( can_use )
					ID[make_pair(f,i)] = nextID[LR(f)]++;
			}
		}

		// then create the graph
		graph G( nextID[0] + nextID[1] );
		for(int j=0; j<As.size(); ++j)
		{
			pair<int,int> p(Cs[j], As[j]);
			pair<int,int> q(Ds[j], Bs[j]);
			if( ID.count(p) && ID.count(q) )
			{
				int pid = ID[p] + (LR(Cs[j]) ? nextID[0] : 0);
				int qid = ID[q] + (LR(Ds[j]) ? nextID[0] : 0);
				G[pid].push_back(qid);
				G[qid].push_back(pid);
			}
		}
		return make_pair(G, nextID[0]);
	}

	int maxGuards(int N, vector <string> escDescription) 
	{
		// parse the input
		vector<int> As, Bs, Cs, Ds, Ks(N);
		{
			stringstream sin;
			copy( escDescription.begin(), escDescription.end(), ostream_iterator<string>(sin,"") );

			for(int A,B,C; sin>>A>>B>>C; )
			{
				{char comma; sin>>comma;}
				--A, --B, --C; int D=(C+1)%N; // to 0-orign
				As.push_back(A);
				Bs.push_back(B);
				Cs.push_back(C);
				Ds.push_back(D);
				Ks[C] = max(Ks[C], A+1);
				Ks[D] = max(Ks[D], B+1);
			}
		}

		// the most simple floor, where the number Ks[msf] of stations is the least
		int msf = min_element(Ks.begin(), Ks.end()) - Ks.begin();

		// try all possibilities at the msf-th floor
		size_t answer = 0;
		for(int mask=0; mask<(1<<Ks[msf]); ++mask)
		{
			// then the rest of the part becomes a bipartite graph
			pair<graph, int> G = generateBipartiteGraph(As,Bs,Cs,Ds,Ks,msf,mask);

			// |MaxIndenepdentSet| == |V|-|MinCover| =(for bipartite graphs)= |V|-|MaxMatch|
			answer = max(answer, G.first.size() - biMatch<100>(G.first,G.second) + bitcnt(mask));
		}
		return answer;
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, MallSecurity().maxGuards(N, escDescription));}
int main(){

CASE(0)
	int N = 10; 
	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 ", 
 "1 9,1 1 10"};
	  vector <string> escDescription(escDescription_, escDescription_+sizeof(escDescription_)/sizeof(*escDescription_)); 
	int _ = 5; 
END
CASE(1)
	int N = 11; 
	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 ", 
 "1 9,1 1 10"};
	  vector <string> escDescription(escDescription_, escDescription_+sizeof(escDescription_)/sizeof(*escDescription_)); 
	int _ = 6; 
END
CASE(2)
	int N = 10; 
	string escDescription_[] = {"1 1 7,1 2 9,2 1", 
 " 8,1 2 6,1 1 8,1 2 3,1 2 2,2 ", 
 "2 4,1 1 1,2 1 2,3 2 3,1 1 5,2 1 1,4 ", 
 "1 7,1 1 10,3 2 5,1 2 5,3 3 1,", 
 "3 2 8,3 1 2,1 1 3,4 4 2,2", 
 " 4 6,4 2 5,2 3 3,6 4 1,5 2 8,1 3 6,1 3 7,", 
 "4 3 8,1 3 8,5 2 3,4 2 8,2 6 7,1 3 9,", 
 "1 1 4,6 1 1,2 3 1,5 1 5,6 1 8,5 ", 
 "2 2,3 2 10,3 3 9,1 5 2,4 1 1,1 5 10"};
	  vector <string> escDescription(escDescription_, escDescription_+sizeof(escDescription_)/sizeof(*escDescription_)); 
	int _ = 25; 
END
CASE(3)
	int N = 13; 
	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"};
	  vector <string> escDescription(escDescription_, escDescription_+sizeof(escDescription_)/sizeof(*escDescription_)); 
	int _ = 50; 
END
/*
CASE(4)
	int N = ; 
	string escDescription_[] = ;
	  vector <string> escDescription(escDescription_, escDescription_+sizeof(escDescription_)/sizeof(*escDescription_)); 
	int _ = ; 
END
*/
}
// END CUT HERE