91eacbb0eb 2017-07-22        kinaba: #include <iostream>
91eacbb0eb 2017-07-22        kinaba: #include <sstream>
91eacbb0eb 2017-07-22        kinaba: #include <iomanip>
91eacbb0eb 2017-07-22        kinaba: #include <vector>
91eacbb0eb 2017-07-22        kinaba: #include <string>
91eacbb0eb 2017-07-22        kinaba: #include <map>
91eacbb0eb 2017-07-22        kinaba: #include <set>
91eacbb0eb 2017-07-22        kinaba: #include <algorithm>
91eacbb0eb 2017-07-22        kinaba: #include <numeric>
91eacbb0eb 2017-07-22        kinaba: #include <iterator>
91eacbb0eb 2017-07-22        kinaba: #include <functional>
91eacbb0eb 2017-07-22        kinaba: #include <complex>
91eacbb0eb 2017-07-22        kinaba: #include <queue>
91eacbb0eb 2017-07-22        kinaba: #include <stack>
91eacbb0eb 2017-07-22        kinaba: #include <cmath>
91eacbb0eb 2017-07-22        kinaba: #include <cassert>
91eacbb0eb 2017-07-22        kinaba: #include <tuple>
91eacbb0eb 2017-07-22        kinaba: using namespace std;
91eacbb0eb 2017-07-22        kinaba: typedef long long LL;
91eacbb0eb 2017-07-22        kinaba: typedef complex<double> CMP;
91eacbb0eb 2017-07-22        kinaba: 
91eacbb0eb 2017-07-22        kinaba: template<typename Vert=int, typename Flow=int, int NV = 50>
91eacbb0eb 2017-07-22        kinaba: class MaxFlow
91eacbb0eb 2017-07-22        kinaba: {
91eacbb0eb 2017-07-22        kinaba: 	vector<int> G[NV];
91eacbb0eb 2017-07-22        kinaba: 	Flow F[NV][NV];
91eacbb0eb 2017-07-22        kinaba: 
91eacbb0eb 2017-07-22        kinaba: public:
91eacbb0eb 2017-07-22        kinaba: 	void addEdge(Vert s, Vert t)
91eacbb0eb 2017-07-22        kinaba: 	{
91eacbb0eb 2017-07-22        kinaba: 		G[s].push_back(t);
91eacbb0eb 2017-07-22        kinaba: 		G[t].push_back(s);
91eacbb0eb 2017-07-22        kinaba: 		F[s][t] = 1;
91eacbb0eb 2017-07-22        kinaba: 		F[t][s] = 1;
91eacbb0eb 2017-07-22        kinaba: 	}
91eacbb0eb 2017-07-22        kinaba: 
91eacbb0eb 2017-07-22        kinaba: 	Flow calc(Vert S, Vert D)
91eacbb0eb 2017-07-22        kinaba: 	{
91eacbb0eb 2017-07-22        kinaba: 		for (Flow total = 0;; ) {
91eacbb0eb 2017-07-22        kinaba: 			// Do BFS and compute the level for each node.
91eacbb0eb 2017-07-22        kinaba: 			int LV[NV] = { 0 };
91eacbb0eb 2017-07-22        kinaba: 			vector<int> Q(1, S);
91eacbb0eb 2017-07-22        kinaba: 			for (int lv = 1; !Q.empty(); ++lv) {
91eacbb0eb 2017-07-22        kinaba: 				vector<int> Q2;
91eacbb0eb 2017-07-22        kinaba: 				for (size_t i = 0; i != Q.size(); ++i) {
91eacbb0eb 2017-07-22        kinaba: 					const vector<int>& ne = G[Q[i]];
91eacbb0eb 2017-07-22        kinaba: 					for (size_t j = 0; j != ne.size(); ++j)
91eacbb0eb 2017-07-22        kinaba: 						if (F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j] != S)
91eacbb0eb 2017-07-22        kinaba: 							LV[ne[j]] = lv, Q2.push_back(ne[j]);
91eacbb0eb 2017-07-22        kinaba: 				}
91eacbb0eb 2017-07-22        kinaba: 				Q.swap(Q2);
91eacbb0eb 2017-07-22        kinaba: 			}
91eacbb0eb 2017-07-22        kinaba: 
91eacbb0eb 2017-07-22        kinaba: 			// Destination is now unreachable. Done.
91eacbb0eb 2017-07-22        kinaba: 			if (!LV[D])
91eacbb0eb 2017-07-22        kinaba: 				return total;
91eacbb0eb 2017-07-22        kinaba: 
91eacbb0eb 2017-07-22        kinaba: 			// Iterating DFS.
91eacbb0eb 2017-07-22        kinaba: 			bool blocked[NV] = {};
91eacbb0eb 2017-07-22        kinaba: 			total += dinic_dfs(S, D, LV, 0x7fffffff, blocked);
91eacbb0eb 2017-07-22        kinaba: 		}
91eacbb0eb 2017-07-22        kinaba: 	}
91eacbb0eb 2017-07-22        kinaba: 
91eacbb0eb 2017-07-22        kinaba: private:
91eacbb0eb 2017-07-22        kinaba: 	Flow dinic_dfs(int v, int D, int LV[], Flow flow_in, bool blocked[])
91eacbb0eb 2017-07-22        kinaba: 	{
91eacbb0eb 2017-07-22        kinaba: 		Flow flow_out = 0;
91eacbb0eb 2017-07-22        kinaba: 		for (size_t i = 0; i != G[v].size(); ++i) {
91eacbb0eb 2017-07-22        kinaba: 			int u = G[v][i];
91eacbb0eb 2017-07-22        kinaba: 			if (LV[v] + 1 == LV[u] && F[v][u]) {
91eacbb0eb 2017-07-22        kinaba: 				Flow f = min(flow_in - flow_out, F[v][u]);
91eacbb0eb 2017-07-22        kinaba: 				if (u == D || !blocked[u] && (f = dinic_dfs(u, D, LV, f, blocked))>0) {
91eacbb0eb 2017-07-22        kinaba: 					F[v][u] -= f;
91eacbb0eb 2017-07-22        kinaba: 					F[u][v] += f;
91eacbb0eb 2017-07-22        kinaba: 					flow_out += f;
91eacbb0eb 2017-07-22        kinaba: 					if (flow_in == flow_out) return flow_out;
91eacbb0eb 2017-07-22        kinaba: 				}
91eacbb0eb 2017-07-22        kinaba: 			}
91eacbb0eb 2017-07-22        kinaba: 		}
91eacbb0eb 2017-07-22        kinaba: 		blocked[v] = (flow_out == 0);
91eacbb0eb 2017-07-22        kinaba: 		return flow_out;
91eacbb0eb 2017-07-22        kinaba: 	}
91eacbb0eb 2017-07-22        kinaba: };
91eacbb0eb 2017-07-22        kinaba: 
91eacbb0eb 2017-07-22        kinaba: class AngelDemonGame { public:
91eacbb0eb 2017-07-22        kinaba: 	string winner(vector <string> G, int A, int D)
91eacbb0eb 2017-07-22        kinaba: 	{
91eacbb0eb 2017-07-22        kinaba: 		const int N = G.size();
91eacbb0eb 2017-07-22        kinaba: 		if (D >= N - 1)
91eacbb0eb 2017-07-22        kinaba: 			return "Demon"; // by cutting all the edges around 0.
91eacbb0eb 2017-07-22        kinaba: 
91eacbb0eb 2017-07-22        kinaba: 		// Since A>=2, there are at least (n-1) way
91eacbb0eb 2017-07-22        kinaba: 		//   0--(n-1) or 0--k--(n-1) for all k
91eacbb0eb 2017-07-22        kinaba: 		// possible and disjoint paths. Devil cannot prevent all of them.
91eacbb0eb 2017-07-22        kinaba: 		// If and only if Angle can make mincut > D, Angle certainly wins.
91eacbb0eb 2017-07-22        kinaba: 		// Otherwise Demon may luckily choose the mincut.
91eacbb0eb 2017-07-22        kinaba: 		return canMakeMinCutLargerThanD(N, G, A, D) ? "Angel" : "Unknown";
91eacbb0eb 2017-07-22        kinaba: 	}
91eacbb0eb 2017-07-22        kinaba: 
91eacbb0eb 2017-07-22        kinaba: 	bool canMakeMinCutLargerThanD(int N, vector<string> G, int A, int D)
91eacbb0eb 2017-07-22        kinaba: 	{
91eacbb0eb 2017-07-22        kinaba: 		if (G[0][N - 1] == 'N') {
91eacbb0eb 2017-07-22        kinaba: 			G[0][N - 1] = G[N - 1][0] = 'Y';
91eacbb0eb 2017-07-22        kinaba: 			--A;
91eacbb0eb 2017-07-22        kinaba: 		}
91eacbb0eb 2017-07-22        kinaba: 
91eacbb0eb 2017-07-22        kinaba: 		set<int> Lchance, Rchance;
91eacbb0eb 2017-07-22        kinaba: 		for (int u = 1; u < N - 1; ++u) {
91eacbb0eb 2017-07-22        kinaba: 			if (G[0][u] == 'N') Lchance.insert(u);
91eacbb0eb 2017-07-22        kinaba: 			if (G[u][N-1] == 'N') Rchance.insert(u);
91eacbb0eb 2017-07-22        kinaba: 		}
91eacbb0eb 2017-07-22        kinaba: 
91eacbb0eb 2017-07-22        kinaba: 		int cur = minCut(N, G);
91eacbb0eb 2017-07-22        kinaba: 		while(cur <= D && A > 0) {
91eacbb0eb 2017-07-22        kinaba: 			for (int u : Lchance) {
91eacbb0eb 2017-07-22        kinaba: 				G[0][u] = G[u][0] = 'Y';
91eacbb0eb 2017-07-22        kinaba: 				if (minCut(N, G) > cur) {
91eacbb0eb 2017-07-22        kinaba: 					--A;
91eacbb0eb 2017-07-22        kinaba: 					++cur;
91eacbb0eb 2017-07-22        kinaba: 					Lchance.erase(u);
91eacbb0eb 2017-07-22        kinaba: 					goto next;
91eacbb0eb 2017-07-22        kinaba: 				}
91eacbb0eb 2017-07-22        kinaba: 				G[0][u] = G[u][0] = 'N';
91eacbb0eb 2017-07-22        kinaba: 			}
91eacbb0eb 2017-07-22        kinaba: 			for (int u : Rchance) {
91eacbb0eb 2017-07-22        kinaba: 				G[u][N-1] = G[N-1][u] = 'Y';
91eacbb0eb 2017-07-22        kinaba: 				if (minCut(N, G) > cur) {
91eacbb0eb 2017-07-22        kinaba: 					--A;
91eacbb0eb 2017-07-22        kinaba: 					++cur;
91eacbb0eb 2017-07-22        kinaba: 					Rchance.erase(u);
91eacbb0eb 2017-07-22        kinaba: 					goto next;
91eacbb0eb 2017-07-22        kinaba: 				}
91eacbb0eb 2017-07-22        kinaba: 				G[u][N - 1] = G[N - 1][u] = 'N';
91eacbb0eb 2017-07-22        kinaba: 			}
91eacbb0eb 2017-07-22        kinaba: 
91eacbb0eb 2017-07-22        kinaba: 			if (!Lchance.empty()) {
91eacbb0eb 2017-07-22        kinaba: 				int u = *Lchance.begin();
91eacbb0eb 2017-07-22        kinaba: 				G[0][u] = G[u][0] = 'Y';
91eacbb0eb 2017-07-22        kinaba: 				Lchance.erase(u);
91eacbb0eb 2017-07-22        kinaba: 				--A;
91eacbb0eb 2017-07-22        kinaba: 				goto next;
91eacbb0eb 2017-07-22        kinaba: 			}
91eacbb0eb 2017-07-22        kinaba: 			if (!Rchance.empty()) {
91eacbb0eb 2017-07-22        kinaba: 				int u = *Rchance.begin();
91eacbb0eb 2017-07-22        kinaba: 				G[0][u] = G[u][0] = 'Y';
91eacbb0eb 2017-07-22        kinaba: 				Rchance.erase(u);
91eacbb0eb 2017-07-22        kinaba: 				--A;
91eacbb0eb 2017-07-22        kinaba: 				goto next;
91eacbb0eb 2017-07-22        kinaba: 			}
91eacbb0eb 2017-07-22        kinaba: 		next:;
91eacbb0eb 2017-07-22        kinaba: 		}
91eacbb0eb 2017-07-22        kinaba: 
91eacbb0eb 2017-07-22        kinaba: 		return cur > D;
91eacbb0eb 2017-07-22        kinaba: 	}
91eacbb0eb 2017-07-22        kinaba: 
91eacbb0eb 2017-07-22        kinaba: 	int minCut(int N, const vector<string>& G)
91eacbb0eb 2017-07-22        kinaba: 	{
91eacbb0eb 2017-07-22        kinaba: 		MaxFlow<> mf;
91eacbb0eb 2017-07-22        kinaba: 		for (int u = 0; u < N; ++u)
91eacbb0eb 2017-07-22        kinaba: 			for (int v = u + 1; v < N; ++v)
91eacbb0eb 2017-07-22        kinaba: 				if (G[u][v] == 'Y')
91eacbb0eb 2017-07-22        kinaba: 					mf.addEdge(u, v);
91eacbb0eb 2017-07-22        kinaba: 		return mf.calc(0, N - 1);
91eacbb0eb 2017-07-22        kinaba: 	}
91eacbb0eb 2017-07-22        kinaba: };
91eacbb0eb 2017-07-22        kinaba: 
91eacbb0eb 2017-07-22        kinaba: // BEGIN CUT HERE
91eacbb0eb 2017-07-22        kinaba: #include <ctime>
91eacbb0eb 2017-07-22        kinaba: double start_time; string timer()
91eacbb0eb 2017-07-22        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
91eacbb0eb 2017-07-22        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
91eacbb0eb 2017-07-22        kinaba:  { os << "{ ";
91eacbb0eb 2017-07-22        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
91eacbb0eb 2017-07-22        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
91eacbb0eb 2017-07-22        kinaba: void verify_case(const string& Expected, const string& Received) {
91eacbb0eb 2017-07-22        kinaba:  bool ok = (Expected == Received);
91eacbb0eb 2017-07-22        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
91eacbb0eb 2017-07-22        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
91eacbb0eb 2017-07-22        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
91eacbb0eb 2017-07-22        kinaba: #define END	 verify_case(_, AngelDemonGame().winner(G, A, D));}
91eacbb0eb 2017-07-22        kinaba: int main(){
91eacbb0eb 2017-07-22        kinaba: 
91eacbb0eb 2017-07-22        kinaba: CASE(0)
91eacbb0eb 2017-07-22        kinaba: 	string G_[] = {"NYNY",
91eacbb0eb 2017-07-22        kinaba:  "YNYY",
91eacbb0eb 2017-07-22        kinaba:  "NYNN",
91eacbb0eb 2017-07-22        kinaba:  "YYNN"};
91eacbb0eb 2017-07-22        kinaba: 	  vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
91eacbb0eb 2017-07-22        kinaba: 	int A = 2;
91eacbb0eb 2017-07-22        kinaba: 	int D = 2;
91eacbb0eb 2017-07-22        kinaba: 	string _ = "Angel";
91eacbb0eb 2017-07-22        kinaba: END
91eacbb0eb 2017-07-22        kinaba: CASE(1)
91eacbb0eb 2017-07-22        kinaba: 	string G_[] = {"NYNY",
91eacbb0eb 2017-07-22        kinaba:  "YNYY",
91eacbb0eb 2017-07-22        kinaba:  "NYNN",
91eacbb0eb 2017-07-22        kinaba:  "YYNN"};
91eacbb0eb 2017-07-22        kinaba: 	  vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
91eacbb0eb 2017-07-22        kinaba: 	int A = 6;
91eacbb0eb 2017-07-22        kinaba: 	int D = 6;
91eacbb0eb 2017-07-22        kinaba: 	string _ = "Demon";
91eacbb0eb 2017-07-22        kinaba: END
91eacbb0eb 2017-07-22        kinaba: CASE(2)
91eacbb0eb 2017-07-22        kinaba: 	string G_[] = {"NNNN",
91eacbb0eb 2017-07-22        kinaba:  "NNNN",
91eacbb0eb 2017-07-22        kinaba:  "NNNN",
91eacbb0eb 2017-07-22        kinaba:  "NNNN"};
91eacbb0eb 2017-07-22        kinaba: 	  vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
91eacbb0eb 2017-07-22        kinaba: 	int A = 2;
91eacbb0eb 2017-07-22        kinaba: 	int D = 2;
91eacbb0eb 2017-07-22        kinaba: 	string _ = "Unknown";
91eacbb0eb 2017-07-22        kinaba: END
91eacbb0eb 2017-07-22        kinaba: CASE(3)
91eacbb0eb 2017-07-22        kinaba: 	string G_[] = {"NYNNNY",
91eacbb0eb 2017-07-22        kinaba:  "YNNYNN",
91eacbb0eb 2017-07-22        kinaba:  "NNNNYN",
91eacbb0eb 2017-07-22        kinaba:  "NYNNNN",
91eacbb0eb 2017-07-22        kinaba:  "NNYNNN",
91eacbb0eb 2017-07-22        kinaba:  "YNNNNN"};
91eacbb0eb 2017-07-22        kinaba: 	  vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
91eacbb0eb 2017-07-22        kinaba: 	int A = 4;
91eacbb0eb 2017-07-22        kinaba: 	int D = 4;
91eacbb0eb 2017-07-22        kinaba: 	string _ = "Unknown";
91eacbb0eb 2017-07-22        kinaba: END
91eacbb0eb 2017-07-22        kinaba: CASE(4)
91eacbb0eb 2017-07-22        kinaba: 	string G_[] = {"NYNNNY",
91eacbb0eb 2017-07-22        kinaba:  "YNNYNN",
91eacbb0eb 2017-07-22        kinaba:  "NNNNYN",
91eacbb0eb 2017-07-22        kinaba:  "NYNNNN",
91eacbb0eb 2017-07-22        kinaba:  "NNYNNN",
91eacbb0eb 2017-07-22        kinaba:  "YNNNNN"};
91eacbb0eb 2017-07-22        kinaba: 	  vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
91eacbb0eb 2017-07-22        kinaba: 	int A = 8;
91eacbb0eb 2017-07-22        kinaba: 	int D = 4;
91eacbb0eb 2017-07-22        kinaba: 	string _ = "Angel";
91eacbb0eb 2017-07-22        kinaba: END
91eacbb0eb 2017-07-22        kinaba: CASE(5)
91eacbb0eb 2017-07-22        kinaba: 	string G_[] = {"NYNNNY",
91eacbb0eb 2017-07-22        kinaba:  "YNNYNN",
91eacbb0eb 2017-07-22        kinaba:  "NNNNYN",
91eacbb0eb 2017-07-22        kinaba:  "NYNNNN",
91eacbb0eb 2017-07-22        kinaba:  "NNYNNN",
91eacbb0eb 2017-07-22        kinaba:  "YNNNNN"};
91eacbb0eb 2017-07-22        kinaba: 	  vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
91eacbb0eb 2017-07-22        kinaba: 	int A = 4;
91eacbb0eb 2017-07-22        kinaba: 	int D = 8;
91eacbb0eb 2017-07-22        kinaba: 	string _ = "Demon";
91eacbb0eb 2017-07-22        kinaba: END
91eacbb0eb 2017-07-22        kinaba: CASE(6)
91eacbb0eb 2017-07-22        kinaba: 	string G_[] = { "NNNN","NNNN","NNNN","NNNN" };
91eacbb0eb 2017-07-22        kinaba: 	  vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
91eacbb0eb 2017-07-22        kinaba: 	int A = 4;
91eacbb0eb 2017-07-22        kinaba: 	int D = 2;
91eacbb0eb 2017-07-22        kinaba: 	string _ = "Unknown";
91eacbb0eb 2017-07-22        kinaba: END
91eacbb0eb 2017-07-22        kinaba: /*
91eacbb0eb 2017-07-22        kinaba: CASE(7)
91eacbb0eb 2017-07-22        kinaba: 	string G_[] = ;
91eacbb0eb 2017-07-22        kinaba: 	  vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
91eacbb0eb 2017-07-22        kinaba: 	int A = ;
91eacbb0eb 2017-07-22        kinaba: 	int D = ;
91eacbb0eb 2017-07-22        kinaba: 	string _ = ;
91eacbb0eb 2017-07-22        kinaba: END
91eacbb0eb 2017-07-22        kinaba: */
91eacbb0eb 2017-07-22        kinaba: }
91eacbb0eb 2017-07-22        kinaba: // END CUT HERE