Artifact Content
Not logged in

Artifact ce17f42a8e0e96e12b7b8730ccbb33954d13632c


#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 <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

template<typename Vert=int, typename Flow=int, int NV = 50>
class MaxFlow
{
	vector<int> G[NV];
	Flow F[NV][NV];

public:
	void addEdge(Vert s, Vert t)
	{
		G[s].push_back(t);
		G[t].push_back(s);
		F[s][t] = 1;
		F[t][s] = 1;
	}

	Flow calc(Vert S, Vert D)
	{
		for (Flow total = 0;; ) {
			// Do BFS and compute the level for each node.
			int LV[NV] = { 0 };
			vector<int> Q(1, S);
			for (int lv = 1; !Q.empty(); ++lv) {
				vector<int> Q2;
				for (size_t i = 0; i != Q.size(); ++i) {
					const vector<int>& ne = G[Q[i]];
					for (size_t j = 0; j != ne.size(); ++j)
						if (F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j] != S)
							LV[ne[j]] = lv, Q2.push_back(ne[j]);
				}
				Q.swap(Q2);
			}

			// Destination is now unreachable. Done.
			if (!LV[D])
				return total;

			// Iterating DFS.
			bool blocked[NV] = {};
			total += dinic_dfs(S, D, LV, 0x7fffffff, blocked);
		}
	}

private:
	Flow dinic_dfs(int v, int D, int LV[], Flow flow_in, bool blocked[])
	{
		Flow flow_out = 0;
		for (size_t i = 0; i != G[v].size(); ++i) {
			int u = G[v][i];
			if (LV[v] + 1 == LV[u] && F[v][u]) {
				Flow f = min(flow_in - flow_out, F[v][u]);
				if (u == D || !blocked[u] && (f = dinic_dfs(u, D, LV, f, blocked))>0) {
					F[v][u] -= f;
					F[u][v] += f;
					flow_out += f;
					if (flow_in == flow_out) return flow_out;
				}
			}
		}
		blocked[v] = (flow_out == 0);
		return flow_out;
	}
};

class AngelDemonGame { public:
	string winner(vector <string> G, int A, int D)
	{
		const int N = G.size();
		if (D >= N - 1)
			return "Demon"; // by cutting all the edges around 0.

		// Since A>=2, there are at least (n-1) way
		//   0--(n-1) or 0--k--(n-1) for all k
		// possible and disjoint paths. Devil cannot prevent all of them.
		// If and only if Angle can make mincut > D, Angle certainly wins.
		// Otherwise Demon may luckily choose the mincut.
		return canMakeMinCutLargerThanD(N, G, A, D) ? "Angel" : "Unknown";
	}

	bool canMakeMinCutLargerThanD(int N, vector<string> G, int A, int D)
	{
		if (G[0][N - 1] == 'N') {
			G[0][N - 1] = G[N - 1][0] = 'Y';
			--A;
		}

		set<int> Lchance, Rchance;
		for (int u = 1; u < N - 1; ++u) {
			if (G[0][u] == 'N') Lchance.insert(u);
			if (G[u][N-1] == 'N') Rchance.insert(u);
		}

		int cur = minCut(N, G);
		while(cur <= D && A > 0) {
			for (int u : Lchance) {
				G[0][u] = G[u][0] = 'Y';
				if (minCut(N, G) > cur) {
					--A;
					++cur;
					Lchance.erase(u);
					goto next;
				}
				G[0][u] = G[u][0] = 'N';
			}
			for (int u : Rchance) {
				G[u][N-1] = G[N-1][u] = 'Y';
				if (minCut(N, G) > cur) {
					--A;
					++cur;
					Rchance.erase(u);
					goto next;
				}
				G[u][N - 1] = G[N - 1][u] = 'N';
			}

			if (!Lchance.empty()) {
				int u = *Lchance.begin();
				G[0][u] = G[u][0] = 'Y';
				Lchance.erase(u);
				--A;
				goto next;
			}
			if (!Rchance.empty()) {
				int u = *Rchance.begin();
				G[0][u] = G[u][0] = 'Y';
				Rchance.erase(u);
				--A;
				goto next;
			}
		next:;
		}

		return cur > D;
	}

	int minCut(int N, const vector<string>& G)
	{
		MaxFlow<> mf;
		for (int u = 0; u < N; ++u)
			for (int v = u + 1; v < N; ++v)
				if (G[u][v] == 'Y')
					mf.addEdge(u, v);
		return mf.calc(0, N - 1);
	}
};

// 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 string& Expected, const string& 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(_, AngelDemonGame().winner(G, A, D));}
int main(){

CASE(0)
	string G_[] = {"NYNY",
 "YNYY",
 "NYNN",
 "YYNN"};
	  vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_)); 
	int A = 2; 
	int D = 2; 
	string _ = "Angel"; 
END
CASE(1)
	string G_[] = {"NYNY",
 "YNYY",
 "NYNN",
 "YYNN"};
	  vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_)); 
	int A = 6; 
	int D = 6; 
	string _ = "Demon"; 
END
CASE(2)
	string G_[] = {"NNNN",
 "NNNN",
 "NNNN",
 "NNNN"};
	  vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_)); 
	int A = 2; 
	int D = 2; 
	string _ = "Unknown"; 
END
CASE(3)
	string G_[] = {"NYNNNY",
 "YNNYNN",
 "NNNNYN",
 "NYNNNN",
 "NNYNNN",
 "YNNNNN"};
	  vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_)); 
	int A = 4; 
	int D = 4; 
	string _ = "Unknown"; 
END
CASE(4)
	string G_[] = {"NYNNNY",
 "YNNYNN",
 "NNNNYN",
 "NYNNNN",
 "NNYNNN",
 "YNNNNN"};
	  vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_)); 
	int A = 8; 
	int D = 4; 
	string _ = "Angel"; 
END
CASE(5)
	string G_[] = {"NYNNNY",
 "YNNYNN",
 "NNNNYN",
 "NYNNNN",
 "NNYNNN",
 "YNNNNN"};
	  vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_)); 
	int A = 4; 
	int D = 8; 
	string _ = "Demon"; 
END
CASE(6)
	string G_[] = { "NNNN","NNNN","NNNN","NNNN" };
	  vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_)); 
	int A = 4; 
	int D = 2; 
	string _ = "Unknown";
END
/*
CASE(7)
	string G_[] = ;
	  vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_)); 
	int A = ; 
	int D = ; 
	string _ = ; 
END
*/
}
// END CUT HERE