Cod sursa(job #2421131)

Utilizator NaritaandreiCNAINarita Andrei NaritaandreiCNAI Data 14 mai 2019 12:39:07
Problema Obiective Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.31 kb
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
FILE *f,*g;
struct graph
{
    int node,next;
}v[33002],v2[33002];
vector <int> a[33002];
int start[33002],start2[33002],been[33002],t[18][33002],lvl[33002],up[18][33002],lg2[33002],st[33002];
int n,m,cate;
void read()
{   int x,y,k=0;
    fscanf(f,"%d %d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        fscanf(f,"%d %d",&x,&y);
        v[++k].node=y;
        v[k].next=start[x];
        start[x]=k;

        v2[k].node=x;
        v2[k].next=start2[y];
        start2[y]=k;
    }
}
void dfs(int nod)
{
    been[nod]=1;
    for(int i=start[nod]; i;i=v[i].next)
        if(!been[v[i].node])
            dfs(v[i].node);
    st[++st[0]]=nod;
}
void dfst(int nod)
{
    been[nod]=1;
    for(int i=start2[nod]; i;i=v2[i].next)
        if(!been[v2[i].node])
            dfst(v2[i].node);
    been[nod]=cate;
}
void tare_conexe()
{
    for(int i=1; i<=n; i++)
        if(!been[i])
            dfs(i);
    for(int i=1; i<=n;i++)
        been[i]=0;
    for(int i=n; i>=1; i--)
        if(!been[st[i]])
        {
            cate++;
            dfst(st[i]);
        }
}
void gen_arb()
{   int k=0;
    for(int i=1; i<=n; i++)
        for(int j=start[i]; j; j=v[j].next)
        {
            if(been[i]!=been[v[j].node])
            {
               a[been[i]].push_back(been[v[j].node]);
               //a[been[v[j].node]].push_back(been[i]);
            }
        }
    for(int i=1; i<=cate; i++)
        sort(a[i].begin(),a[i].end());
}
void logarithm()
{
    for(int i=2; i<=n; i++)
        lg2[i]=lg2[i/2]+1;
}
void build_rmq()
{
    for(int i=1; i<=16; i++)
        for(int j=1; j<=cate; j++)
            t[i][j]=t[i-1][t[i-1][j]], up[i][j]=up[i-1][up[i-1][j]];
}
void dfs3(int nod, int dad)
{
    t[0][nod]=dad;
    up[0][nod]=dad;
    lvl[nod]=lvl[dad]+1;
    for(int i=0; i<a[nod].size(); i++)
    {
        if(!lvl[a[nod][i]])
            dfs3(a[nod][i],nod);
        else
        {
            if(lvl[up[0][a[nod][i]]]>lvl[nod])
                up[0][a[nod][i]]=nod;
        }
    }
}
int lca(int x, int y)
{   int aux,k;
    if(lvl[x]<lvl[y])
    {
        aux=x;
        x=y;
        y=aux;
    }
    k=lvl[x]-lvl[y];
    for(int i=0; i<=16;i++)
        if(k & (1<<i))
            x=t[i][x];
    if(x==y)
        return x;
    for(int i=16 ; i>=0; i--)
        if(t[i][x]!=t[i][y])
            x=t[i][x], y=t[i][y];
    return t[0][x];
}
int goo(int node, int lim)
{   int i, ans=0;
    if(node == lim)
        return 0;
    for(int i=16; i>=0; i--)
        if(lvl[up[i][node]]>lvl[lim])
        {
            ans+=(1<<i);
            node=up[i][node];
        }
    return ans+1;
}
void solve()
{   int x,y,l;
    tare_conexe();
    gen_arb();
    dfs3(1,0);
    for(int i=cate; i; i--)
        if(up[0][i]<up[0][t[0][i]])
            up[0][t[0][i]]=up[0][i];
    build_rmq();
    fscanf(f,"%d",&m);
    for(int i=1; i<=m;i++)
    {
        fscanf(f,"%d %d",&x,&y);
        x=been[x];
        y=been[y];
        l=lca(x,y);
        fprintf(g,"%d\n",goo(x,l));
    }
}

int main()
{
    f=fopen("obiective.in","r");
    g=fopen("obiective.out","w");
    read();
    solve();
    fclose(f);
    fclose(g);
    return 0;
}