Cod sursa(job #922097)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 21 martie 2013 22:09:26
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
// Considerand cazul in care am un singur pion, pot face o dinamica DP[i]=1 daca in cazul in care pionul e aflat in nodul i
// primul jucator castiga
// Se observa ca in cazul in care am mai multi pioni, exista doar o stare cand primul jucator pierde sigur
// si anume cand toate nodurile in care sa afla pioni au DP[i]=0
// Daca exista noduri cu pioni in ele si DP[i]=1, atunci mut din acele noduri pionurile in noduri cu DP[i]=0 si al doilea jucator va ajunge
// intr-o stare cu toti DP[i]=0 deci va pierde
#include <fstream>
#include <vector>
#define NM 30010

using namespace std;

ifstream f("pioni.in");
ofstream g("pioni.out");

int T, N, M, K;
int i, j;
vector<int> G[NM];
bool DP[NM];
int Pawns[NM];
bool Vis[NM];

void DF (int Node)
{
    DP[Node]=0;
    Vis[Node]=1;

    for (vector<int>::iterator it=G[Node].begin(); it!=G[Node].end(); ++it)
    {
        if (!Vis[*it]) DF(*it);
        DP[Node]|=!DP[*it];
    }
}

void Solve ()
{
    bool win=0;
    int nr=0;

    for (i=1; i<=K; i++)
    {
        win|=DP[Pawns[i]];
        nr+=DP[Pawns[i]];
    }

    if (win==0)
    {
        g << "Fumeanu\n";
        return;
    }

    g << "Nargy\n";
    g << nr << ' ';

    vector<int>::iterator it;

    for (i=1; i<=K; i++)
        if (DP[Pawns[i]])
        {
            g << Pawns[i] << ' ';
            for (it=G[Pawns[i]].begin(); it!=G[Pawns[i]].end(); ++it)
                if (DP[*it]==0)
                {
                    g << *it << ' ';
                    break;
                }
        }
    g << '\n';

    return;
}

int main ()
{
    f >> T >> N >> M;

    for (i=1; i<=M; i++)
    {
       int a, b;
       f >> a >> b;
       G[a].push_back(b);
    }

    for (i=1; i<=N; i++)
        if (!Vis[i])
            DF(i);

    for (; T>=1; --T)
    {
        f >> K;
        for (i=1; i<=K; i++)
            f >> Pawns[i];
        Solve();
    }

    f.close();
    g.close();

    return 0;
}