Cod sursa(job #2734221)

Utilizator betybety bety bety Data 31 martie 2021 15:42:16
Problema Obiective Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("obiective.in");
ofstream out("obiective.out");
const int lim=1e5+5;
vector<int> vec2[lim];
vector<int> vec[lim];
vector<int> rev[lim];
stack<int> s;
int grupa[lim],cnt;
int n,m,x,y,tst;
bool ok[lim];
void df(int nod)
{
    ok[nod]=true;
    for(int x:vec[nod])
    if(!ok[x]) df(x);
    s.push(nod);
}
void df2(int nod)
{
    ok[nod]=true;
    grupa[nod]=cnt;
    for(int x:rev[nod])
    if(!ok[x]) df2(x);
}
pair<int,int> tree[18][2*lim+5];
int ad[lim],nr;
int poz[lim];
void df3(int nod)
{
    ok[nod]=true;
    tree[0][++nr]={ad[nod],nod};
    poz[nod]=nr;
    for(int x:vec2[nod])
    if(!ok[x])
    {
        ad[x]=ad[nod]+1;
        df3(x);
        tree[0][++nr]={ad[nod],nod};
        poz[nod]=nr;
    }
}
int lg[lim];
void rmq()
{
    for(int i=2;i<=nr;++i)
        lg[i]=lg[i/2]+1;
    for(int p=1;p<=lg[nr];++p)
    for(int i=1;i+(1<<p)-1<=nr;++i)
        tree[p][i]=min(tree[p-1][i],tree[p-1][i+(1<<(p-1))]);
}
int lca(int a,int b)
{
    a=poz[a];
    b=poz[b];
    if(a<b) swap(a,b);
    int d=lg[b-a+1];
    return min(tree[d][a],tree[d][b-(1<<d)+1]).second;
}
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;++i)
    {
        in>>x>>y;
        vec[x].push_back(y);
        rev[y].push_back(x);
    }
    for(int i=1;i<=n;++i)
    if(!ok[i]) df(i);
    memset(ok,0,sizeof(ok));
    while(!s.empty())
    {
        int x=s.top();
        s.pop();
        if(ok[x])
            continue;
        ++cnt;
        df2(x);
    }
    for(int i=1;i<=n;++i)
    for(int x:vec[i])
    if(grupa[i]!=grupa[x])
        vec2[grupa[i]].push_back(grupa[x]);
    memset(ok,0,sizeof(ok));
    df3(1);
    rmq();
    in>>tst;
    while(tst--)
    {
        in>>x>>y;
        int a=lca(grupa[x],grupa[y]);
        out<<ad[grupa[x]]-ad[grupa[a]]<<'\n';
    }
    return 0;
}