Pagini recente » Cod sursa (job #1395329) | Rezultatele filtrării | Cod sursa (job #1639394) | Borderou de evaluare (job #2208627) | Cod sursa (job #3212882)
#include <bits/stdc++.h>
#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
///#include <tryhardmode>
///#include <GODMODE::ON>
using namespace std;
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser& operator >> (int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
InParser& operator >> (long long &n) {
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
long long sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
InParser fin ("obiective.in");
ofstream fout ("obiective.out");
const int NMAX=32e4+5;
vector<int>comp[NMAX];
vector<int>rev[NMAX];
vector<int>v2[NMAX];
vector<int>v[NMAX];
stack<int>stiva;
int asc2[25][NMAX];
int asc[25][NMAX];
int degree[NMAX];
int color[NMAX];
bool viz[NMAX];
int lvl[NMAX];
int dad[NMAX];
int kon;
void dfs(int p)
{
viz[p]=true;
for(auto i:v[p])
{
if(!viz[i])
dfs(i);
}
stiva.push(p);
}
void dfsc(int p)
{
viz[p]=true;
color[p]=kon;
comp[kon].push_back(p);
for(auto i:rev[p])
{
if(!viz[i])
dfsc(i);
}
}
void dfs_euler(int p,int tata)
{
int e;
viz[p]=true;
lvl[p]=lvl[tata]+1;
for(e=1;e<=20;e++)
asc[e][p]=asc[e-1][asc[e-1][p]];
for(auto i:v2[p])
if(!dad[i] || lvl[p]<lvl[dad[p]])
dad[i]=p;
for(auto i:v2[p])
{
if(!viz[i] && tata!=i)
{
asc[0][i]=p;
dfs_euler(i,p);
if(!dad[p] || lvl[dad[i]]<lvl[dad[p]])
dad[p]=dad[i];
}
}
}
int lca(int x,int y)
{
int level,e;
if(lvl[x]<lvl[y])
swap(x,y);
level=lvl[x]-lvl[y];
for(e=20;e>=0;e--)
{
if(level & (1<<e))
x=asc[e][x];
}
if(x==y)
return x;
for(e=20;e>=0;e--)
{
if(asc[e][x]!=asc[e][y])
{
x=asc[e][x];
y=asc[e][y];
}
}
return asc[0][x];
}
int main()
{
ios_base::sync_with_stdio(false);
fout.tie(NULL);
int n,m,q,i,j,root=0;
fin>>n>>m;
for(i=1;i<=m;i++)
{
int x,y;
fin>>x>>y;
v[x].push_back(y);
rev[y].push_back(x);
}
for(i=1;i<=n;i++)
{
if(!viz[i])
dfs(i);
}
for(i=1;i<=n;i++)
viz[i]=false;
while(!stiva.empty())
{
int p=stiva.top();
if(!viz[p])
{
kon++;
dfsc(p);
}
stiva.pop();
}
for(i=1;i<=n;i++)
{
for(auto j:v[i])
{
if(color[j]!=color[i])
{
v2[color[i]].push_back(color[j]);
degree[color[j]]++;
}
}
}
for(i=1;i<=n;i++)
viz[i]=false;
for(i=1;i<=kon;i++)
{
sort(v2[i].begin(),v2[i].end());
v2[i].erase(unique(v2[i].begin(),v2[i].end()),v2[i].end());
}
for(i=1;i<=kon;i++)
if(degree[i]==0)
root=i;
dfs_euler(root,0);
for(i=1;i<=kon;i++)
asc2[0][i]=dad[i];
for(int e=1;e<=20;e++)
for(i=1;i<=kon;i++)
asc2[e][i]=asc2[e-1][asc2[e-1][i]];
fin>>q;
while(q--)
{
int x,y,lac;
fin>>x>>y;
lac=lca(color[x],color[y]);
if(lac==color[x])
fout<<0<<"\n";
else
{
int total=0;
x=color[x];
for(int e=20;e>=0;e--)
{
if(lvl[asc2[e][x]]>lvl[lac])
{
total+=(1<<e);
x=asc2[e][x];
}
}
fout<<total+1<<"\n";
}
}
fout.close();
return 0;
}