3562021-10-28 14:16:13Kevinke12Utazás (40)cpp14Elfogadva 40/40159ms26680 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ÖsszpontTesztVerdiktIdőMemória
base40/40
1Elfogadva0/08ms14408 KiB
2Elfogadva0/097ms18564 KiB
3Elfogadva1/18ms15568 KiB
4Elfogadva2/27ms15588 KiB
5Elfogadva1/18ms15576 KiB
6Elfogadva2/28ms15600 KiB
7Elfogadva2/28ms15652 KiB
8Elfogadva2/213ms16028 KiB
9Elfogadva2/212ms15792 KiB
10Elfogadva2/213ms16084 KiB
11Elfogadva2/235ms17088 KiB
12Elfogadva3/334ms17628 KiB
13Elfogadva3/337ms18096 KiB
14Elfogadva3/337ms18652 KiB
15Elfogadva3/337ms19140 KiB
16Elfogadva3/339ms19676 KiB
17Elfogadva3/372ms21340 KiB
18Elfogadva3/3138ms24728 KiB
19Elfogadva3/3159ms26680 KiB