Cod sursa(job #2023386)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 18 septembrie 2017 21:05:35
Problema Santa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <bits/stdc++.h>
#define no_solution {cout << "No chance\n"; return 0;}

using namespace std;

const int Nmax = 45005;

vector<int> v[Nmax], a, path;
vector< vector<int> > bcc;
int low[Nmax], level[Nmax], Node, Finish, Start, n, m, i, x, y;
bool good[Nmax];
stack<int> st;

void dfs(int node, int dad = 0)
{
    low[node] = level[node] = level[dad] + 1;
    st.push(node);
    if(node == Finish) good[node] = 1;

    for(auto it : v[node])
    {
        if(it == dad) continue;
        if(low[it])
        {
            low[node] = min(low[node], level[it]);
            continue;
        }

        dfs(it, node);
        good[node] |= good[it];
        low[node] = min(low[node], low[it]);

        if(low[it] >= level[node])
        {
            vector<int> comp;
            while(st.top() != it)
            {
                comp.push_back(st.top());
                st.pop();
            }

            comp.push_back(it);
            comp.push_back(node);
            st.pop();

            if(!good[it]) continue;

            bcc.push_back(comp);
            a.push_back(node);
        }
    }
}

bool sol(int x, int y, int sz, bool ok = 0)
{
    if(ok) path.push_back(x);
    good[x] = 1;

    if(sz == 1 && (x==y || !y)) return 1;
    if(x == y || sz == 1)
    {
        if(ok) path.pop_back();
        good[x] = 0;
        return 0;
    }

    for(auto it : v[x])
        if(!good[it] && sol(it, y, sz-1, 1))
            return 1;

    if(ok) path.pop_back();
    good[x] = 0;
    return 0;
}

int main()
{
    freopen("santa.in", "r", stdin);
    freopen("santa.out", "w", stdout);
    cin.sync_with_stdio(false);

    cin >> n >> m;
    for(i=1; i<=m; ++i)
    {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    cin >> Start >> Finish >> Node;
    a.push_back(Node);
    dfs(Start);

    if(find(bcc[0].begin(), bcc[0].end(), Node) == bcc[0].end())
    {
        reverse(bcc.begin(), bcc.end());
        reverse(a.begin(), a.end());
    }

    if(find(bcc[0].begin(), bcc[0].end(), Node) == bcc[0].end()) no_solution;
    a.front() = Node, a.back() = 0;

    path.push_back(Node);
    memset(good, 0, sizeof(good));
    for(i=0; i<bcc.size(); ++i)
        if(!sol(a[i], a[i+1], bcc[i].size()))
            no_solution;

    cout << path.size() << '\n';
    for(auto it : path) cout << it << ' ';

    return 0;
}