#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 2e5;
const int mod = 1e9 + 7;
/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/
// BBRBBL
signed main(){
int n, m; cin >> n >> m;
vector<pair<int, int> > g[n+1];
vector<pair<int, int> > edge;
vector<int> dir(m, 0);
for(int i = 0;i < m; i++){
int a, b; cin >> a >> b;
edge.push_back({a, b});
g[a].push_back({b, i});
g[b].push_back({a, i});
}
int q; cin >> q;
vector<pair<int, int> > Q(q);
vector<pair<int, int>> vert[n+1];
for(int i = 0;i < q; i++){
cin >> Q[i].ff >> Q[i].ss;
vert[Q[i].ff].push_back({Q[i].ss, 0});
vert[Q[i].ss].push_back({Q[i].ff, 1});
}
vector<int> out(n+1, -1);
vector<int> tin(n+1), tout(n+1);
vector<int> ans(m, -1);
vector<int> used(n+1, 0);
int timer = 0;
map<pair<int, int>, int> mp;
function<void(int, int)> bridges=[&](int v, int p){
tin[v] = ++timer;
out[v] = timer;
used[v] = 1;
int flag = 0;
for(auto [to, idx] : g[v]){
if(make_pair(v, to) == edge[idx]) dir[idx] = 1;
if(!used[to]){
bridges(to, v);
out[v] = min(out[v], out[to]);
}else{
if(to == p){
if(flag){
out[v] = min(out[v], tin[to]);
}
flag = 1;
}else{
out[v] = min(out[v], tin[to]);
}
}
}
if(p != -1 && tin[v] == out[v]){
mp[make_pair(min(v, p), max(v, p))] = 1;
}
tout[v] = timer;
};
for(int i = 1;i <= n; i++){
if(!used[i]){
bridges(i, -1);
}
}
for(int i = 1;i <= n; i++) used[i] = 0;
pair<int, int> mn[n+1], mx[n+1];
function<void(int, int)> dfs=[&](int v, int p){
used[v] = 1;
mn[v] = {n+1, -1};
mx[v] = {-1, -1};
for(auto [u, t] : vert[v]){
mn[v] = min(mn[v], make_pair(tin[u], t));
mx[v] = max(mx[v], make_pair(tout[u], t));
}
vector<pair<int, int> > tmp;
for(auto [to, idx] : g[v]){
if(used[to]) continue;
dfs(to, v);
mn[v] = min(mn[v], mn[to]);
mx[v] = max(mx[v], mx[to]);
if(out[to] > tin[v]){
tmp.push_back({to, idx});
}
}
for(auto [to, idx] : tmp){
if(mn[to].ff < tin[to]){
ans[idx] = mn[to].ss;
}
if(mx[to].ff > tout[to]){
ans[idx] = mx[to].ss;
}
}
};
for(int i = 1;i <= n; i++){
if(!used[i]) dfs(i, i);
}
for(int i = 0;i < m; i++){
auto [a, b] = edge[i];
if(a > b) swap(a, b);
if(!mp.count({a, b})){
ans[i] = -1;
}
}
for(int i = 0;i < m; i++){
if(ans[i] == -1){
cout << 'B';
}else{
ans[i]^= dir[i];
if(ans[i] == 0) cout << 'L';
else cout << 'R';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
