356 2021. 10. 28 14:16:13 Kevinke12 Utazás (40) cpp14 Elfogadva 40/40 159ms 26680 KiB
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int N, M, Q, be1, be2;
vector<int> ellista[200005];
int h[200005]; //0-undefined, 1-nyero, -1 veszto
bool voltmar[200005]; //0-undefined, 1-nyero, -1 veszto
vector<int> kerd;

struct alma
{
    int cs;
    int be=0;
};
alma sor[200005];
bool Rend(alma a, alma b)
{
    return (a.be<b.be);
}
int Mely(int cs)
{
    voltmar[cs]=true;

    int alatta=0;
    for(int a:ellista[cs])
    {
        if(voltmar[a]==false)
        {
            Mely(a);
        }
        alatta=min(alatta, h[a]);
    }
    if((alatta==-1)) //Minden nyero
    {
        h[cs]=1;
        return 1;
    }
    else
    {
        h[cs]=-1;
        return -1;
    }
}

int main()
{
    cin >> N >> M >> Q;
    for(int i = 0; i < Q; i++)
    {
        cin >> be1; kerd.push_back(be1);
    }
    for(int i = 1; i <= N; i++) sor[i].cs=i;
    for(int i = 0; i < M; i++)
    {
        cin >> be1 >> be2;
        ellista[be1].push_back(be2);
        sor[be2].be++;
    }
    sort(sor+1, sor+N+1, Rend);
    for(int i = 1;i <= N; i++)
    {
        if(h[sor[i].cs]==0)
            Mely(sor[i].cs);
    }

    /*for(int i = 1;i <= N; i++)
    {
        cout << i << ":" << h[i] << "\n";
    }*/
    for(int a:kerd)
    {
        if(h[a]==1)
            cout << "A\n";
        else
            cout << "B\n";
    }
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 40/40
1 Elfogadva 0/0 8ms 14408 KiB
2 Elfogadva 0/0 97ms 18564 KiB
3 Elfogadva 1/1 8ms 15568 KiB
4 Elfogadva 2/2 7ms 15588 KiB
5 Elfogadva 1/1 8ms 15576 KiB
6 Elfogadva 2/2 8ms 15600 KiB
7 Elfogadva 2/2 8ms 15652 KiB
8 Elfogadva 2/2 13ms 16028 KiB
9 Elfogadva 2/2 12ms 15792 KiB
10 Elfogadva 2/2 13ms 16084 KiB
11 Elfogadva 2/2 35ms 17088 KiB
12 Elfogadva 3/3 34ms 17628 KiB
13 Elfogadva 3/3 37ms 18096 KiB
14 Elfogadva 3/3 37ms 18652 KiB
15 Elfogadva 3/3 37ms 19140 KiB
16 Elfogadva 3/3 39ms 19676 KiB
17 Elfogadva 3/3 72ms 21340 KiB
18 Elfogadva 3/3 138ms 24728 KiB
19 Elfogadva 3/3 159ms 26680 KiB