2253 2023. 01. 06 08:27:43 kohumark Utazás (40) cpp11 Elfogadva 40/40 46ms 8084 KiB
// Example program
#include <bits/stdc++.h>
#define speed cin.tie(0);ios::sync_with_stdio(0)
using namespace std;

int main()
{
    speed;
    int n, m, q;
    cin >> n >> m >> q;
    int ind[q]; for(int i=0; i<q; i++){
	cin >> ind[i];
	ind[i]--;
    }
    
    vector<vector<int>> jaratok; int be[n];
    jaratok.assign(n, vector<int>());
    for(int i=0; i<n; i++) be[i]=0;
    for(int i=0; i<m; i++){
	int a, b;
        cin >> a >> b; a--; b--;
	jaratok[a].push_back(b);
	be[b]++;
    }
    
    queue<int> alap; vector<int> vegso;
    for(int i=0; i<n; i++) if(be[i]==0) alap.push(i);

    while(!alap.empty()){
	int next=alap.front();
	alap.pop();
	for(int i : jaratok[next]){
		be[i]--;
		if(be[i]==0){
		       alap.push(i);
		}
	}
	vegso.push_back(next);
    }

    bool win[n+1];
    for(int i=0; i<n+1; i++) win[i]=false;
    for(int i=n-1; i>-1; i--){
	for(int j : jaratok[vegso[i]]){
		win[vegso[i]] |= ! win[j];
	}
    }

    for(int i=0; i<q; i++) cout << (win[ind[i]] ? "A\n" : "B\n");
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 40/40
1 Elfogadva 0/0 3ms 1824 KiB
2 Elfogadva 0/0 35ms 8084 KiB
3 Elfogadva 1/1 2ms 2268 KiB
4 Elfogadva 2/2 2ms 2464 KiB
5 Elfogadva 1/1 2ms 2632 KiB
6 Elfogadva 2/2 2ms 2852 KiB
7 Elfogadva 2/2 3ms 3256 KiB
8 Elfogadva 2/2 4ms 3960 KiB
9 Elfogadva 2/2 3ms 3756 KiB
10 Elfogadva 2/2 4ms 3904 KiB
11 Elfogadva 2/2 13ms 4684 KiB
12 Elfogadva 3/3 14ms 4700 KiB
13 Elfogadva 3/3 14ms 4916 KiB
14 Elfogadva 3/3 14ms 4932 KiB
15 Elfogadva 3/3 14ms 5240 KiB
16 Elfogadva 3/3 14ms 5492 KiB
17 Elfogadva 3/3 26ms 6416 KiB
18 Elfogadva 3/3 46ms 7876 KiB
19 Elfogadva 3/3 46ms 8056 KiB