This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
//#include "rail.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const ll nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int i,n,m,x,y,fin[nmax],fup[nmax],tim,viz[nmax];
pair<int,int>edg[nmax];
vector<pair<int,int> >a[nmax];
vector<int>brg;
void dfs(int x,int p)
{
viz[x]=1;
fin[x]=fup[x]=++tim;
for(int i=0;i<a[x].size();i++)
{
if(a[x][i].fr==p)continue;
if(viz[a[x][i].fr])fup[x]=min(fup[x],fin[a[x][i].fr]);
else
{
dfs(a[x][i].fr,x);
fup[x]=min(fup[x],fup[a[x][i].fr]);
if(fup[a[x][i].fr]>fin[x])brg.pb(a[x][i].sc);
}
}
}
void dfs2(int x)
{
viz[x]=1;
vl[x]=k;
for(int i=0;i<a[x].size();i++)
{
if(viz[a[x][i].fr] || vb[a[x][i].sc])continue;
dfs2(a[x][i].fr);
}
}
void dfs3(int x,int p)
{
for(int i=0;i<gr[x].size();i++)
{
if(gr[x][i].fr==p)continue;
dfs3(gr[x][i].fr);
val[x]+=val[gr[x][i].fr];
}
}
void bld(int x,int p)
{
viz[x]=1;
vc.pb(x);
tin[x]=++t;
if(p)up[x][0]=p;
else up[x][0]=1;
for(int i=1;i<18;i++)up[x][i]=up[up[x][i-1]][i-1];
for(int i=0;i<gr[x].size();i++)if(gr[x][i].fr!=p)bld(gr[x][i].fr,x);
tout[x]=++t;
}
int anc(int x,int y)
{
return tin[x]<=tin[y] && tout[x]>=tout[y];
}
int lca(int x,int y)
{
if(anc(x,y))return x;
if(anc(y,x))return y;
for(int i=17;i>=0;i--)if(!anc(up[x][i],y))x=up[x][i];
return up[x][0];
}
int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
cin>>n>>m;
for(i=1;i<=m;i++)
{
cin>>x>>y;
a[x].pb(mkp(y,i));
a[y].pb(mkp(x,i));
edg[i]=mkp(x,y);
}
for(i=1;i<=n;i++)
{
if(viz[i])continue;
dfs(i,0);
}
for(i=0;i<brg.size();i++)vb[brg[i]]=1;
for(i=1;i<=m;i++)rs[i]='B';
memset(viz,0,sizeof(viz));
for(i=1;i<=n;i++)
{
if(viz[i])continue;
k++;
dfs2(i);
}
for(i=1;i<=n;i++)
{
for(j=0;j<a[i].size();j++)
{
if(vb[a[i][j].sc])
{
gr[vl[i]].pb(mkp(vl[a[i][j].fr],a[i][j].sc));
gr[vl[a[i][j].fr]].pb(mkp(vl[i],a[i][j].sc));
}
}
}
cin>>nr;
for(i=1;i<=nr;i++)
{
cin>>x>>y;
if(vl[x]!=vl[y])q[vl[x]].pb(vl[y]);
}
memset(viz,0,sizeof(viz));
for(i=1;i<=k;i++)
{
if(viz[i])continue;
vc.clear();
bld(i,0);
for(j=0;j<vc.size();j++)
{
x=vc[j];
for(t=0;t<q[x].size();t++)
{
l=lca(q[x][t],x);
val[x]++;
val[up[l][0]]--;
}
}
dfs3(i,0);
}
return 0;
}
Compilation message (stderr)
oneway.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization("O3")
oneway.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization("unroll-loops")
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:30:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a[x].size();i++)
~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int)':
oneway.cpp:45:2: error: 'vl' was not declared in this scope
vl[x]=k;
^~
oneway.cpp:45:2: note: suggested alternative: 'll'
vl[x]=k;
^~
ll
oneway.cpp:45:8: error: 'k' was not declared in this scope
vl[x]=k;
^
oneway.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a[x].size();i++)
~^~~~~~~~~~~~
oneway.cpp:48:25: error: 'vb' was not declared in this scope
if(viz[a[x][i].fr] || vb[a[x][i].sc])continue;
^~
oneway.cpp:48:25: note: suggested alternative: 'pb'
if(viz[a[x][i].fr] || vb[a[x][i].sc])continue;
^~
pb
oneway.cpp: In function 'void dfs3(int, int)':
oneway.cpp:54:16: error: 'gr' was not declared in this scope
for(int i=0;i<gr[x].size();i++)
^~
oneway.cpp:54:16: note: suggested alternative: 'er'
for(int i=0;i<gr[x].size();i++)
^~
er
oneway.cpp:58:3: error: 'val' was not declared in this scope
val[x]+=val[gr[x][i].fr];
^~~
oneway.cpp: In function 'void bld(int, int)':
oneway.cpp:64:2: error: 'vc' was not declared in this scope
vc.pb(x);
^~
oneway.cpp:64:2: note: suggested alternative: 'rc'
vc.pb(x);
^~
rc
oneway.cpp:65:5: error: 'tin' was not declared in this scope
tin[x]=++t;
^~~
oneway.cpp:65:5: note: suggested alternative: 'tim'
tin[x]=++t;
^~~
tim
oneway.cpp:65:14: error: 't' was not declared in this scope
tin[x]=++t;
^
oneway.cpp:66:10: error: 'up' was not declared in this scope
if(p)up[x][0]=p;
^~
oneway.cpp:66:10: note: suggested alternative: 'p'
if(p)up[x][0]=p;
^~
p
oneway.cpp:67:10: error: 'up' was not declared in this scope
else up[x][0]=1;
^~
oneway.cpp:67:10: note: suggested alternative: 'p'
else up[x][0]=1;
^~
p
oneway.cpp:68:26: error: 'up' was not declared in this scope
for(int i=1;i<18;i++)up[x][i]=up[up[x][i-1]][i-1];
^~
oneway.cpp:68:26: note: suggested alternative: 'p'
for(int i=1;i<18;i++)up[x][i]=up[up[x][i-1]][i-1];
^~
p
oneway.cpp:69:19: error: 'gr' was not declared in this scope
for(int i=0;i<gr[x].size();i++)if(gr[x][i].fr!=p)bld(gr[x][i].fr,x);
^~
oneway.cpp:69:19: note: suggested alternative: 'er'
for(int i=0;i<gr[x].size();i++)if(gr[x][i].fr!=p)bld(gr[x][i].fr,x);
^~
er
oneway.cpp:70:5: error: 'tout' was not declared in this scope
tout[x]=++t;
^~~~
oneway.cpp:70:5: note: suggested alternative: 'stdout'
tout[x]=++t;
^~~~
stdout
oneway.cpp: In function 'int anc(int, int)':
oneway.cpp:74:12: error: 'tin' was not declared in this scope
return tin[x]<=tin[y] && tout[x]>=tout[y];
^~~
oneway.cpp:74:12: note: suggested alternative: 'tim'
return tin[x]<=tin[y] && tout[x]>=tout[y];
^~~
tim
oneway.cpp:74:30: error: 'tout' was not declared in this scope
return tin[x]<=tin[y] && tout[x]>=tout[y];
^~~~
oneway.cpp:74:30: note: suggested alternative: 'stdout'
return tin[x]<=tin[y] && tout[x]>=tout[y];
^~~~
stdout
oneway.cpp: In function 'int lca(int, int)':
oneway.cpp:80:35: error: 'up' was not declared in this scope
for(int i=17;i>=0;i--)if(!anc(up[x][i],y))x=up[x][i];
^~
oneway.cpp:80:35: note: suggested alternative: 'fup'
for(int i=17;i>=0;i--)if(!anc(up[x][i],y))x=up[x][i];
^~
fup
oneway.cpp:81:12: error: 'up' was not declared in this scope
return up[x][0];
^~
oneway.cpp:81:12: note: suggested alternative: 'fup'
return up[x][0];
^~
fup
oneway.cpp: In function 'int main()':
oneway.cpp:102:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<brg.size();i++)vb[brg[i]]=1;
~^~~~~~~~~~~
oneway.cpp:102:27: error: 'vb' was not declared in this scope
for(i=0;i<brg.size();i++)vb[brg[i]]=1;
^~
oneway.cpp:102:27: note: suggested alternative: 'pb'
for(i=0;i<brg.size();i++)vb[brg[i]]=1;
^~
pb
oneway.cpp:103:19: error: 'rs' was not declared in this scope
for(i=1;i<=m;i++)rs[i]='B';
^~
oneway.cpp:103:19: note: suggested alternative: 'rc'
for(i=1;i<=m;i++)rs[i]='B';
^~
rc
oneway.cpp:108:3: error: 'k' was not declared in this scope
k++;
^
oneway.cpp:113:7: error: 'j' was not declared in this scope
for(j=0;j<a[i].size();j++)
^
oneway.cpp:115:7: error: 'vb' was not declared in this scope
if(vb[a[i][j].sc])
^~
oneway.cpp:115:7: note: suggested alternative: 'pb'
if(vb[a[i][j].sc])
^~
pb
oneway.cpp:117:5: error: 'gr' was not declared in this scope
gr[vl[i]].pb(mkp(vl[a[i][j].fr],a[i][j].sc));
^~
oneway.cpp:117:5: note: suggested alternative: 'er'
gr[vl[i]].pb(mkp(vl[a[i][j].fr],a[i][j].sc));
^~
er
oneway.cpp:117:8: error: 'vl' was not declared in this scope
gr[vl[i]].pb(mkp(vl[a[i][j].fr],a[i][j].sc));
^~
oneway.cpp:117:8: note: suggested alternative: 'll'
gr[vl[i]].pb(mkp(vl[a[i][j].fr],a[i][j].sc));
^~
ll
oneway.cpp:122:7: error: 'nr' was not declared in this scope
cin>>nr;
^~
oneway.cpp:122:7: note: suggested alternative: 'n'
cin>>nr;
^~
n
oneway.cpp:126:6: error: 'vl' was not declared in this scope
if(vl[x]!=vl[y])q[vl[x]].pb(vl[y]);
^~
oneway.cpp:126:6: note: suggested alternative: 'll'
if(vl[x]!=vl[y])q[vl[x]].pb(vl[y]);
^~
ll
oneway.cpp:126:19: error: 'q' was not declared in this scope
if(vl[x]!=vl[y])q[vl[x]].pb(vl[y]);
^
oneway.cpp:129:13: error: 'k' was not declared in this scope
for(i=1;i<=k;i++)
^
oneway.cpp:132:3: error: 'vc' was not declared in this scope
vc.clear();
^~
oneway.cpp:132:3: note: suggested alternative: 'rc'
vc.clear();
^~
rc
oneway.cpp:134:7: error: 'j' was not declared in this scope
for(j=0;j<vc.size();j++)
^
oneway.cpp:137:8: error: 't' was not declared in this scope
for(t=0;t<q[x].size();t++)
^
oneway.cpp:137:14: error: 'q' was not declared in this scope
for(t=0;t<q[x].size();t++)
^
oneway.cpp:139:5: error: 'l' was not declared in this scope
l=lca(q[x][t],x);
^
oneway.cpp:140:5: error: 'val' was not declared in this scope
val[x]++;
^~~
oneway.cpp:141:9: error: 'up' was not declared in this scope
val[up[l][0]]--;
^~
oneway.cpp:141:9: note: suggested alternative: 'fup'
val[up[l][0]]--;
^~
fup