Submission #70039199

---

Source Code Expand

/* Code By WCM */
/*
Date:
大致思路：
复杂度：
期望得分：
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <vector>
#include <queue>

using namespace std;

inline int read();
void write(int);
void writeln(int);

const int N = 2e5 + 5;
int T, n, m, K, f[N][21][2];
string s;
vector <int> G[N];

int dfs(int u, int k, int fl) {
	if(k == 0) return (s[u - 1] != 'A');
	if(f[u][k][fl] != -1) return f[u][k][fl];
	int res;
	if(fl == 0) {
		res = 1;
		for(int v : G[u]) {
			int nxt = dfs(v, k - 1, 1);
			if(nxt == 0) { res = 0; break; }
		}
	}
	else {
		res = 0;
		for(int v : G[u]) {
			int nxt = dfs(v, k - 1, 0);
			if(nxt == 1) { res = 1; break; }
		}
	}
	return f[u][k][fl] = res;
}

int main() {

//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);

	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> T;
	while(T--) {
		cin >> n >> m >> K >> s;
		for(int i = 1; i <= n; i++) G[i].clear();
		for(int i = 0, u, v; i < m; i++) {
			cin >> u >> v;
			G[u].push_back(v); 
		}
		for(int i = 1; i <= n; i++)
			for(int j = 0; j <= K * 2; j++)
				f[i][j][0] = f[i][j][1] = -1;
		int ans = dfs(1, K * 2, 0);
		cout << (ans == 0 ? "Alice\n" : "Bob\n");
	}
	
//	printf("\nThe time used: ");
//	printf("%.2lfs",(double)clock()/CLOCKS_PER_SEC);

	return 0;

}

inline int read() {
	int res = 0, f = 1;
	char ch = getchar();
	while( !(ch >= '0' && ch <= '9') ) {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		res = (res << 1) + (res << 3) + (ch ^ 48);
		ch = getchar();
	}
	return res * f;
}

void write(int x) {
	static int sta[35];
	int top = 0;
	do {
		sta[top++] = x % 10;
		x /= 10;
	} while(x);
	while(top) putchar(sta[--top] ^ 48);
}

void writeln(int x) {
	write(x);
	putchar('\n');
}

Submission Info

Judge Result