8158 2024. 01. 12 14:54:20 anon Utazás (40) cpp17 Elfogadva 40/40 56ms 11180 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 40/40
1 Elfogadva 0/0 3ms 1832 KiB
2 Elfogadva 0/0 35ms 9240 KiB
3 Elfogadva 1/1 3ms 2272 KiB
4 Elfogadva 2/2 3ms 2472 KiB
5 Elfogadva 1/1 3ms 2832 KiB
6 Elfogadva 2/2 3ms 2728 KiB
7 Elfogadva 2/2 4ms 3148 KiB
8 Elfogadva 2/2 6ms 3868 KiB
9 Elfogadva 2/2 4ms 3724 KiB
10 Elfogadva 2/2 6ms 4032 KiB
11 Elfogadva 2/2 16ms 5512 KiB
12 Elfogadva 3/3 16ms 5740 KiB
13 Elfogadva 3/3 16ms 6128 KiB
14 Elfogadva 3/3 16ms 6212 KiB
15 Elfogadva 3/3 16ms 6276 KiB
16 Elfogadva 3/3 17ms 6328 KiB
17 Elfogadva 3/3 28ms 7700 KiB
18 Elfogadva 3/3 56ms 10636 KiB
19 Elfogadva 3/3 52ms 11180 KiB