Cod sursa(job #2351721)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 22 februarie 2019 17:26:00
Problema Pioni Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <bits/stdc++.h>

#define MAXN 20005

int T, N, M;
std::vector <int> ADC[MAXN];

inline void AddEdge(int X, int Y) {
    ADC[X].push_back(Y);
}

int DP[MAXN][2];
void DFS(int Vertex, int turn = 0) {
    if (DP[Vertex][turn] != 0) return;

    bool bSink = 1;
    for (auto Edge:ADC[Vertex])
        bSink = 0, DFS(Edge, 1-turn);

    if (bSink) {
        DP[Vertex][turn] = (Vertex + 1) * turn - 1;
        return;
    }

    if (turn == 0) {
        DP[Vertex][turn] = -1;
        for (auto Edge:ADC[Vertex])
            if (DP[Edge][1-turn]) {
                DP[Vertex][turn] = Edge;
                break;
            }
    }
    else {
        DP[Vertex][turn] = ADC[Vertex][0];
        for (auto Edge:ADC[Vertex])
            if (!DP[Edge][1-turn]) {
                DP[Vertex][turn] = -1;
                break;
            }
    }
}

std::ifstream In ("pioni.in");
std::ofstream Out("pioni.out");

void Citire() {
    In >> T >> N >> M;
    for (int i=1, X, Y; i<=M; ++i)
        In >> X >> Y, AddEdge(X, Y);
}

void Rezolvare() {
    for (int i=1; i<=N; ++i)
        if (DP[i][0] == 0)
            DFS(i);

    int K, Arr[MAXN];
    bool Flag;

    while (T--) {
        In >> K;
        Flag = 1;
        for (int i=1; i<=K; ++i) {
            In >> Arr[i];
            Flag &= (DP[Arr[i]][0] != -1);
        }

        if (Flag) {
            Out << "Nargy\n";
            int Count = 0;
            for (int i=1; i<=K; ++i)
                if (DP[Arr[i]][0] != Arr[i])
                    ++ Count;

            Out << Count << ' ';
            for (int i=1; i<=K; ++i)
                if (DP[Arr[i]][0] != Arr[i])
                    Out << Arr[i] << ' ' << DP[Arr[i]][0] << ' ';
            Out << '\n';
        }
        else {
            Out << "Fumeanu\n";
        }
    }
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}