Submission #36907208

---

Source Code Expand

#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long

using namespace std;

const int N = 3e5+5;
vector<int> adj[N];
int dp[N], deg[N];

int get(char c){
	if(c <= 'Z') return c-'A';
	else return c-'a'+26;
}

int encode(string s){
	return get(s[0])+get(s[1])*52+get(s[2])*52*52;
}

signed main(){
	fastio
	int n;
	cin >> n;

	vector<int> ask;
	for(int i = 0; i < n; i++){
		string s;
		cin >> s;
		int u = encode(s.substr(0,3)), v = encode(s.substr(s.size()-3,3));
		adj[v].push_back(u);
		deg[u]++;
		ask.push_back(v);
	}

	queue<int> q;
	for(int i = 0; i < N; i++){
		if(deg[i]==0){
			q.push(i);
			dp[i] = -1;
		}
	}

	while(!q.empty()){
		int u = q.front(); q.pop();
		for(auto v : adj[u]){
			if(dp[v] == 0){
				deg[v]--;
				if(dp[u] == -1){
					dp[v] = 1;
					q.push(v);
				}else if(deg[v]==0){
					dp[v] = -1, q.push(v);
				}
			}
		}
	}

	for(auto u : ask){
		if(dp[u] == -1) cout << "Takahashi\n";
		else if(dp[u] == 1) cout << "Aoki\n";
		else cout << "Draw\n";
	}
}

Submission Info

Judge Result