#ifdef LOCAL
#include "D:\debug.h"
#else
#define cebug(...) "anHiepORZ"
#endif
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define int long long
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
vector<int> g[N];
vector<pair<int,int>> t[N];
map<pair<int,int>,int> bridge;
int vis[N];
int tin[N], low[N];
int timedfs = 0;
void dfs(int u, int p = 0){
timedfs++;
low[u] = tin[u] = timedfs;
for(int v : g[u]){
if(v == p) continue;
if(tin[v] == 0){
dfs(v, u);
if(low[v] == tin[v]){
// int _u = u, _v = v.first;
// if(_v < _u) swap(u)
bridge[make_pair(u, v)] = 1;
bridge[make_pair(v, u)] = 1;
}
low[u] = min(low[u], low[v]);
}
else low[u] = min(low[u], tin[v]);
}
}
// vector<int> edge;
// int cnt;
// map<pair<int,int>, int> dm;
int nenso[N];
int ans[N];
int idx;
void dfs2(int u){
nenso[u] = idx;
for(int v: g[u]){
if(bridge[{u, v}]) continue;
if(vis[v]) continue;
vis[v] = 1;
dfs2(v);
}
}
int up[N][20], h[N], ps[N];
int vv[N];
void dfs3(int u, int p = 0, int hh = 0){
h[u]= hh;
for(auto v: t[u]){
if(v.first == p) continue;
vv[v.first] = 1;
up[v.first][0] = u;
for(int i = 1; i < 20; i++){
up[v.first][i] = up[up[v.first][i - 1]][i - 1];
}
dfs3(v.first, u, hh + 1);
}
}
int lca(int u, int v){
if(h[u] > h[v]) swap(u, v);
int diff = h[v] - h[u];
for(int i = 0; i < 20; i++){
if(diff & (1<<i)) v = up[v][i];
}
if(u == v) return u;
// cebug(u, v);
for(int i = 19; i >= 0; i--){
int _u = up[u][i], _v = up[v][i];
if(_u != _v) u = _u, v = _v;
}
return up[u][0];
}
map<pair<int,int>,int> dit;
void cal(int u, int p = 0){
for(auto v: t[u]){
if(v.first == p) continue;
vv[v.first]=1;
cal(v.first, u);
ps[u] += ps[v.first];
}
for(auto v: t[u]){
if(v.first == p) continue;
// cebug(u, v.first, dit[{u, v.first}]);
if(ps[v.first] == 0) ans[v.second] = 1;
else if(ps[v.first] > 0){
if(dit[{u, v.first}]) ans[v.second] = 2;
else ans[v.second] = 3;
}
else{
if(dit[{u, v.first}]) ans[v.second] = 3;
else ans[v.second] = 2;
}
}
}
void solve(){
int n, m;
cin >> n >> m;
vector<pair<pair<int,int>, int>> e;
map<pair<int,int>, int> qr;
map<pair<int,int>, int> dm;
for(int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
dm[{u, v}] = 1;
qr[{u, v}] = i;
qr[{v, u}] = i;
g[u].push_back(v);
g[v].push_back(u);
e.push_back({make_pair(u, v), i});
}
//ans 1: B, 2: R, 3: L
for(int i = 1; i <= n; i++){
if(tin[i] == 0) dfs(i);
}
map<pair<int,int>, int> sus;
for(auto &x : e){
if(bridge[x.first] == 0) ans[x.second] = 1;
else{
int _u = x.first.first, _v = x.first.second;
if(_v < _u) swap(_u, _v);
if(sus[{_u, _v}] == 1) ans[x.second] = 1;
sus[{_u, _v}] = 1;
}
}
idx = 1;
for(int i = 1; i <= n; i++){
if(vis[i] == 0){
vis[i] = 1;
dfs2(i);
//edge
idx++;
}
}
for(auto b : bridge){
if(b.second == 0) continue;
int _u = b.first.first, _v = b.first.second;
if(_v < _u) swap(_u, _v);
if(sus[{_u, _v}] > 1) continue;
cerr << nenso[b.first.first] << " " << nenso[b.first.second] << endl;
if(dm[b.first]) dit[{nenso[b.first.first], nenso[b.first.second]}] = 1;
t[nenso[b.first.first]].push_back({nenso[b.first.second], qr[b.first]});
}
// for(int i = 1; i <= idx; i++){
// cebug(i, t[i]);
// }
for(int i = 1; i <= idx; i++){
if(vv[i] == 0){
vv[i] = 1;
dfs3(i);
}
}
int p;
cin >> p;
for(int i = 1; i <= p; i++){
int u, v; cin >> u >> v;
u = nenso[u], v= nenso[v];
if(u == v) continue;
int l = lca(u, v);
// cebug(u, v, l);
//u->l
ps[u]++;
ps[v]--;
}
memset(vv, 0, sizeof(vv));
for(int i = 1; i <= idx; i++){
if(vv[i] ==0){
vv[i] = 1;
cal(i);
}
}
for(int i = 1; i <= m; i++){
if(ans[i] == 1) cout << "B";
else if(ans[i] == 2) cout << "L";
else cout << "R";
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tc; tc = 1;
while(tc--)
solve();
return 0;
}
Compilation message
oneway.cpp: In function 'void solve()':
oneway.cpp:192:13: warning: unused variable 'l' [-Wunused-variable]
192 | int l = lca(u, v);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12636 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
12632 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12636 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
12632 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12636 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
12632 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
