Cod sursa(job #2515948)

Utilizator ArmivioIlas Armand Viorel Armivio Data 29 decembrie 2019 20:43:58
Problema Santa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <bits/stdc++.h>
#define NMAX 45005
using namespace std;
ifstream f("santa.in");
ofstream g("santa.out");
int n,m,s,e,q,nrSpir,nrq,sol[NMAX];
bitset <NMAX> adj[NMAX];
bitset <NMAX> spir;
bitset <NMAX> viz;
bool findSpiritNodes(int node)
{

    viz[node]=true;
    if(node==e)
    {
        spir[node]=true;
        nrSpir++;
        return true;
    }
    int i;
    bool ok=0;
    for(i=1;i<=n;i++)
    {
        if(adj[node][i] && !viz[i])
        {
            ok=(ok || findSpiritNodes(i));
        }
    }
    spir[node]=ok;
    if(ok)
    {
        nrSpir++;
        return true;
    }
    return false;
}
bool bkt(int node, int k)
{
    sol[k]=node;
    viz[node]=true;
    if(k==nrSpir) return true;
    int i;
    bool ok;
    for(i=1;i<=n;i++)
    {
        if(adj[node][i] && !viz[i] && spir[i])
        {
            ok=bkt(i,k+1);
            if(ok) return true;
        }
    }
    sol[k]=0;
    viz[node]=false;
    return false;
}
int main()
{
    int i,j,k;
    f>>n>>m;
    for(k=1;k<=m;k++)
    {
        f>>i>>j;
        adj[i][j]=adj[j][i]=true;
    }
    f>>s>>e>>q;
    bool ok=findSpiritNodes(s);
    for(i=1;i<=n;i++) viz[i]=false;
    ok=bkt(q,1);
    if(ok)
    {
        g<<nrSpir<<'\n';
        for(i=1;i<=nrSpir;i++)
            g<<sol[i]<<' ';
    }
    else g<<"No chance";
    return 0;
}

/*bool normalDF(int node)
{// nu a mai fost utilizat in ultima versiune oups :)))
    int i;
    viz[node]=true;
    nrq++;
    st.push(node);
    if(nrq==nrSpir) return true;
    for(i=1;i<=n;i++)
    {
        if(adj[node][i] && !viz[i] && spir[i])
        {
            if(normalDF(i)) return true;
        }
    }
    nrq--;
    st.pop();
    viz[node]=false;
    return false;
}*/