#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int T,n,m,cnt=0,Time=0,Num[100005],Low[100005],In[100005],Out[100005],Pre[100005],h[100005],P[100005][20];
int add1[100005],add2[100005],sub1[100005],sub2[100005];
bool FEdge[100005],Pass1[100005],Pass2[100005];
vector<ii> Edge,gg[100005];
vector<int> g[100005];
void FindBridge(int u,int preid)
{
Num[u]=Low[u]=++cnt;
for(int i=0;i<gg[u].size();i++)
{
int v=gg[u][i].first;
int id=gg[u][i].second;
if(Num[v]==0)
{
FindBridge(v,id);
Low[u]=min(Low[u],Low[v]);
if(Low[v]>=Num[v])
FEdge[id]=true;
}
else
if(id!=preid)
Low[u]=min(Low[u],Num[v]);
}
}
void DFSComponent(int u,int kk)
{
Pre[u]=kk;
for(int i=0;i<gg[u].size();i++)
{
int v=gg[u][i].first;
int id=gg[u][i].second;
if(FEdge[id]==false&&Pre[v]==0)
DFSComponent(v,kk);
}
}
void DFSHigh(int u,int high)
{
h[u]=high;
In[u]=++Time;
for(int i=0;i<g[u].size();i++)
if(h[g[u][i]]==0)
{
P[g[u][i]][0]=u;
DFSHigh(g[u][i],high+1);
}
Out[u]=Time;
}
int LCA(int u,int v)
{
for(int k=17;k>=0;k--)
if(h[P[u][k]]>=h[v])
u=P[u][k];
else
if(h[P[v][k]]>=h[u])
v=P[v][k];
for(int k=17;k>=0;k--)
if(P[u][k]!=P[v][k])
{
u=P[u][k];
v=P[v][k];
}
while(u!=v)
{
u=P[u][0];
v=P[v][0];
}
return u;
}
int Search(int u,int v)
{
int l=0,r=g[u].size()-1;
while(l<=r)
{
int mid=(l+r)/2;
if(In[g[u][mid]]<=In[v]&&Out[v]<=Out[g[u][mid]])
return g[u][mid];
if(In[v]<In[g[u][mid]])
r=mid-1;
else
l=mid+1;
}
}
void SumDFS(int u,int root,int s1,int s2)
{
Pass1[u]=(s1>0);
Pass2[u]=(s2>0);
for(int i=0;i<g[u].size();i++)
if(g[u][i]!=root)
SumDFS(g[u][i],u,s1-sub1[u]+add1[g[u][i]],s2-sub2[u]+add2[g[u][i]]);
}
int main()
{
ios_base::sync_with_stdio(false);
//freopen("TEST.INP","r",stdin);
cin>>n>>m;
int u,v,Count=0;
for(int i=1;i<=m;i++)
{
cin>>u>>v;
Edge.push_back(ii(u,v));
gg[u].push_back(ii(v,i));
gg[v].push_back(ii(u,i));
}
for(int i=1;i<=n;i++)
if(Num[i]==0)
FindBridge(i,0);
for(int i=1;i<=n;i++)
if(Pre[i]==0)
DFSComponent(i,++Count);
for(int i=0;i<Edge.size();i++)
{
int u=Pre[Edge[i].first];
int v=Pre[Edge[i].second];
if(u!=v)
{
g[u].push_back(v);
g[v].push_back(u);
}
}
for(int i=1;i<=n;i++)
if(h[i]==0)
DFSHigh(i,1);
for(int k=1;k<=17;k++)
for(int i=1;i<=Count;i++)
P[i][k]=P[P[i][k-1]][k-1];
cin>>T;
while(T--)
{
cin>>u>>v;
u=Pre[u];
v=Pre[v];
int w=LCA(u,v);
if(u!=w)
{
add2[Search(w,u)]++;
sub2[u]++;
}
if(v!=w)
{
add1[Search(w,v)]++;
sub1[v]++;
}
}
SumDFS(1,1,add1[1],add2[1]);
for(int i=0;i<Edge.size();i++)
{
int u=Pre[Edge[i].first];
int v=Pre[Edge[i].second];
if(u==v)
cout<<'B';
else
if((u==P[v][0]&&Pass1[v]==true)||(v==P[u][0]&&Pass2[u]==true))
cout<<'R';
else
cout<<'L';
}
}
Compilation message
oneway.cpp: In function 'void FindBridge(int, int)':
oneway.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<gg[u].size();i++)
~^~~~~~~~~~~~~
oneway.cpp: In function 'void DFSComponent(int, int)':
oneway.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<gg[u].size();i++)
~^~~~~~~~~~~~~
oneway.cpp: In function 'void DFSHigh(int, int)':
oneway.cpp:47:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[u].size();i++)
~^~~~~~~~~~~~
oneway.cpp: In function 'void SumDFS(int, int, int, int)':
oneway.cpp:97:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[u].size();i++)
~^~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:121:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<Edge.size();i++)
~^~~~~~~~~~~~
oneway.cpp:156:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<Edge.size();i++)
~^~~~~~~~~~~~
oneway.cpp: In function 'int Search(int, int)':
oneway.cpp:91:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
5112 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
5112 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
5112 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |