81582024-01-12 14:54:20anonUtazás (40)cpp17Accepted 40/4056ms11180 KiB
#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long long ll;
bool solve(bool player, ll city, const ll N, const vector<vector<ll>> &graph, vector<ll> &dp) {
    ll key = city + player * N;
    ll &ans = dp[key];
    if(ans != -1)
        return ans;
    if(player) {
        ans = false;
        for(const auto &x : graph[city]) {
            if(solve(false, x, N, graph, dp)) {
                ans = true;
                break;
            }
        }
    }
    else {
        ans = true;
        for(const auto &x : graph[city]) {
            if(!solve(true, x, N, graph, dp)) {
                ans = false;
                break;
            }
        }
    }
    return ans;
}
int main() {
    FastIO;
    ll i, u, v, N, M, Q;
    cin >> N >> M >> Q;
    vector<ll> cities(Q);
    for(i = 0; i < Q; i++) {
        cin >> cities[i];
        cities[i]--;
    }
    vector<vector<ll>> graph(N);
    for(i = 0; i < M; i++) {
        cin >> u >> v;
        graph[u - 1].push_back(v - 1);
    }
    vector<ll> dp(N * 2, -1);
    for(const auto &x : cities)
        cout << (solve(true, x, N, graph, dp) ? 'A' : 'B') << '\n';
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base40/40
1Accepted0/03ms1832 KiB
2Accepted0/035ms9240 KiB
3Accepted1/13ms2272 KiB
4Accepted2/23ms2472 KiB
5Accepted1/13ms2832 KiB
6Accepted2/23ms2728 KiB
7Accepted2/24ms3148 KiB
8Accepted2/26ms3868 KiB
9Accepted2/24ms3724 KiB
10Accepted2/26ms4032 KiB
11Accepted2/216ms5512 KiB
12Accepted3/316ms5740 KiB
13Accepted3/316ms6128 KiB
14Accepted3/316ms6212 KiB
15Accepted3/316ms6276 KiB
16Accepted3/317ms6328 KiB
17Accepted3/328ms7700 KiB
18Accepted3/356ms10636 KiB
19Accepted3/352ms11180 KiB