Cod sursa(job #2023391)

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

using namespace std;

const int Nmax = 45005, buf_size = 1<<17;

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

void read(int &x)
{
    x = 0;
    while(buffer[pos] < '0' || buffer[pos] > '9')
    {
        ++pos;
        if(pos == buf_size) pos = 0, fread(buffer, 1, buf_size, stdin);
    }


    while(buffer[pos] >= '0' && buffer[pos] <= '9')
    {
        x = x*10 + buffer[pos] - '0';
        ++pos;
        if(pos == buf_size) pos = 0, fread(buffer, 1, buf_size, stdin);
    }
}

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);

    pos = 0, fread(buffer, 1, buf_size, stdin);

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

    read(Start); read(Finish); read(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;

    for(i=1; i<=n; ++i) good[i] = 1;

    for(auto c : bcc)
        for(auto it : c)
            good[it] = 0;

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

        for(auto it : bcc[i]) good[it] = 1;
    }

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

    return 0;
}