#include <bits/stdc++.h>
//#define double double
#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
using namespace std;
struct edge{
int b=1;
int rev=0;
int i=1;
};
int t,m;
vector<vector<edge>>E;
vector<int>pre, low;
vector<vector<int>>low_constrained;
vector<vector<vector<int>>>rests;
vector<int>orient;
int counter=0;
void dfs(int v, int i)
{
pre[v]=counter++;
low[v]=pre[v];
rep(i,2) low_constrained[i][v] = pre[v];
for(edge w : E[v])
{
if(w.i==i) continue;
if(pre[w.b]!=-1) {low[v]=min(low[w.b], low[v]); continue;}
dfs(w.b, w.i);
if(low[w.b]==pre[w.b]) // edge w is a bridge
{
rep(i,2) {
if(low_constrained[i][w.b]<=pre[v])
orient[w.i] = (w.rev+i+1) % 2;
}
}
low[v]=min(low[w.b], low[v]);
rep(i,2) low_constrained[i][v] = min(low_constrained[i][v], low_constrained[i][w.b]);
}
rep(i,2)
{
for(int w : rests[i][v])
{
low_constrained[i][v] = min(low_constrained[i][w], low_constrained[i][v]);
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin>>n>>m;
E.resize(n);
rep(i, m)
{
int a,b;
cin>>a>>b;
a--; b--;
E[a].push_back({b, 0, i});
E[b].push_back({a, 1, i});
}
pre.assign(n, -1);
low.assign(n, -1);
low_constrained.assign(2, vector<int>(n, 1e16));
orient.assign(m, 2);
rests.assign(2, vector<vector<int>>(n));
int p;
cin>>p;
rep(i,p)
{
int a,b;
cin>>a>>b;
a--; b--;
rests[0][a].push_back(b);
rests[1][b].push_back(a);
}
rep(i, n)
{
if(pre[i]!=-1||E[i].size()>1) continue;
dfs(i, -1);
}
for(int o : orient)
{
if(o==0) cout<<"R";
if(o==1) cout<<"L";
if(o==2) cout<<"B";
}
cout<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
