#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define int long long
#define getbit(u,i) ((u>>i)&1)
#define N 100001
using namespace std;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
int n,m,q,num[N],low[N],F[N],Dp[N],l[N],r[N],cnt,Count,h[N],p[N][18],mask[N];
stack<int> st;
vector<int> g[N];
vector<ii> vec[N];
string ans;
void visit(int u,int pre)
{
low[u]=num[u]=++cnt;
st.push(u);
int cur=0;
for(int v : g[u])
{
if(pre!=v||cur==1)
{
if(num[v]) low[u]=min(low[u],num[v]);
else
{
visit(v,u);
low[u]=min(low[u],low[v]);
}
}
else cur++;
}
if(num[u]==low[u])
{
int v;
Count++;
do
{
v=st.top();
mask[v]=Count;
st.pop();
} while(v!=u);
}
}
void dfs(int u,int pre)
{
num[u]=1;
h[u]=h[pre]+1;
p[u][0]=pre;
for(int i=1;i<=17;i++)
{
p[u][i]=p[p[u][i-1]][i-1];
}
for(ii v : vec[u])
{
if(v.x==pre) continue;
dfs(v.x,u);
}
}
int lca(int u,int v)
{
if(h[u]<h[v]) swap(u,v);
for(int i=17;i>=0;i--)
{
if(h[p[u][i]]>=h[v]) u=p[u][i];
}
if(u==v) return u;
for(int i=17;i>=0;i--)
{
if(p[u][i]!=p[v][i])
{
u=p[u][i];
v=p[v][i];
}
}
return p[u][0];
}
void calc(int u,int pre)
{
for(ii v : vec[u])
{
if(v.x==pre) continue;
calc(v.x,u);
Dp[v.y]=F[v.x];
F[u]+=F[v.x];
}
}
signed main()
{
if(fopen("demo.inp","r"))
{
freopen("demo.inp","r",stdin);
freopen("demo.out","w",stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
g[u].pb(v); l[i]=u;
g[v].pb(u); r[i]=v;
}
for(int i=1;i<=n;i++)
{
if(!num[i]) visit(i,i);
}
for(int i=1;i<=m;i++)
{
int lhs=mask[l[i]],rhs=mask[r[i]];
if(lhs!=rhs)
{
vec[lhs].pb({rhs,i});
vec[rhs].pb({lhs,i});
}
}
memset(num,0,sizeof(num));
for(int i=1;i<=n;i++)
{
if(!num[i]) dfs(i,i);
}
cin>>q;
while(q--)
{
int u,v;
cin>>u>>v;
u=mask[u]; v=mask[v];
int anc=lca(u,v);
F[u]++;
F[v]--;
}
calc(1,0);
for(int i=1;i<=m;i++)
{
if(Dp[i]==0) ans+='B';
else
{
if(h[mask[l[i]]]<h[mask[r[i]]])
{
if(Dp[i]<0) ans+='R';
else ans+='L';
}
else
{
if(Dp[i]<0) ans+='L';
else ans+='R';
}
}
}
cout<<ans;
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:132:13: warning: unused variable 'anc' [-Wunused-variable]
132 | int anc=lca(u,v);
| ^~~
oneway.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | freopen("demo.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | freopen("demo.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
11612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
11612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
11612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
