Cod sursa(job #2500052)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 27 noiembrie 2019 10:32:47
Problema Obiective Scor 70
Compilator cpp-64 Status done
Runda guritza Marime 3.11 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
vector <int> graph[32005];
vector <int> graph_inv[32005];
int _stack[32005];
int _stack_size;
int n,m,i,a,b,q,l;
bool vis[32005];
void dfs_inv (int node)
{
    vis[node]=true;
    for (auto it: graph_inv[node])
        if (!vis[it])
            dfs_inv(it);
    _stack[++ _stack_size]=node;
}
int which_scc[32005],degs[32005],h[32005],fathers[15][32005];
void dfs (int node, int scc)
{
    vis[node]=true;
    which_scc[node]=scc;

    for (auto it: graph[node])
        if (!vis[it])
            dfs(it, scc);
}
vector <int> new_graph[32005],tree_graph[32005];
void dfs_lca (int node)
{
    h[node] = h[fathers[0][node]]+1;
    for (i=1; i<15; ++i)
        fathers[i][node]=fathers[i-1][fathers[i - 1][node]];
    for (auto it: tree_graph[node])
    {
        fathers[0][it]=node;
        dfs_lca(it);
    }
}

int lca (int a, int b)
{
    if (h[a]>h[b])
        swap(a, b);
    for (i=14; i>=0; --i)
        if (h[fathers[i][b]]>=h[a])
            b=fathers[i][b];
    if(a==b)
        return a;
    for (i=14; i>=0; --i)
    if (fathers[i][a] != fathers[i][b])
    {
        a=fathers[i][a];
        b=fathers[i][b];
    }
    return fathers[0][a];
}

int sus[15][32005];
void dfs_sus1(int node)
{
    for (auto it: tree_graph[node])
    {
        dfs_sus1(it);
        if (h[sus[0][it]] < h[sus[0][node]])
            sus[0][node]=sus[0][it];
    }
}
void dfs_sus2(int node)
{
    for (int i=1; i<15; ++i)
        sus[i][node] = sus[i - 1][sus[i - 1][node]];
    for (auto it: tree_graph[node])
        dfs_sus2(it);
}
int ask(int a, int l)
{
    int ans=0;
    if (a==l)
        return 0;
    for(i=14; i>=0; --i)
        if (h[sus[i][a]]>h[l])
        {
            a=sus[i][a];
            ans+=(1<<i);
        }
    return 1+ans;
}
int main()
{
    freopen("obiective.in","r",stdin);
    freopen("obiective.out","w",stdout);
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d",&a,&b);
        graph[a].push_back(b);
        graph_inv[b].push_back(a);
    }
    for(i=1; i<=n; ++i)
        if(!vis[i])
            dfs_inv(i);
    memset(vis, 0, sizeof(vis));
    int sccs=0;
    for (int i=n; i; --i)
        if (!vis[_stack[i]])
            dfs(_stack[i], ++sccs);
    for(i=1; i<=n; ++i)
        for (auto it: graph[i])
            if (which_scc[i] != which_scc[it])
                new_graph[which_scc[i]].push_back(which_scc[it]);
    n=sccs;
    for(i=1; i<=n; ++i)
    for(auto it:new_graph[i])
    {
        if (!degs[it])
        {
            ++degs[it];
            tree_graph[i].push_back(it);
        }
    }
    dfs_lca(n);
    for(i=1; i<=n; ++i)
        sus[0][i]=i;
    for(i=1; i<=n; ++i)
        for(auto it: new_graph[i])
            if (h[i]<h[sus[0][it]])
                sus[0][it]=i;
    dfs_sus1(n);
    dfs_sus2(n);
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d",&a,&b);
        a=which_scc[a],b=which_scc[b];
        l=lca(a,b);
        printf("%d\n",ask(a,l));
    }
    return 0;
}