#include<bits/stdc++.h>
using namespace std;
#define range(v) begin(v), end(v)
#define compact(v) v.erase(unique(range(v)), end(v))
template<class T> bool minimize(T& a, T b){
if(a > b) return a = b, true;
return false;
}
template<class T> bool maximize(T& a, T b){
if(a < b) return a = b, true;
return false;
}
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int N = 1e5 + 5;
const int Left = 0;
const int Right = 1;
const int Both = 2;
const char c[] = {'L', 'R', 'B'};
int n, m, low[N], num[N], id[N], dp[N], ans[N], timerDFS, timerSCC;
pair<int, int> e[N], E[N];
vector<pair<int, int>> g[N], G[N];
stack<int> stck;
bitset<N> vst;
void dfsTarjan(int u, int preID){
low[u] = num[u] = ++timerDFS;
stck.push(u);
for(auto [id, dir] : g[u]) if(id != preID){
int v = e[id].first ^ e[id].second ^ u;
if(num[v]) {
minimize(low[u], num[v]);
}
else{
dfsTarjan(v, id);
minimize(low[u], low[v]);
}
}
if(low[u] == num[u]){
++timerSCC;
do{
int v = stck.top(); stck.pop();
id[v] = timerSCC;
low[u] = num[u] = N;
} while(!id[u]);
}
}
void dfsSolve(int u, int preID){
vst[u] = true;
for(auto [id, target] : G[u]) if(preID != id){
int v = E[id].first ^ E[id].second ^ u;
dfsSolve(v, id);
dp[u] += dp[v];
if(dp[v] == 0) ans[id] = Both;
else if(dp[v] < 0) ans[id] = (target == 0 ? Left : Right);
else ans[id] = (target == 0 ? Right : Left);
}
}
void Zero_OP(){
cin >> n >> m;
for(int i = 1; i <= m; ++i){
int u, v;
cin >> u >> v;
g[u].push_back({i, 0});
g[v].push_back({i, 1});
e[i] = {u, v};
}
for(int i = 1; i <= n; ++i){
if(!num[i]) dfsTarjan(1, -1);
}
for(int i = 1; i <= m; ++i){
int u, v;
tie(u, v) = e[i];
E[i] = {id[u], id[v]};
if(id[u] != id[v]){
G[id[u]].push_back({i, 0});
G[id[v]].push_back({i, 1});
}
else ans[i] = Both;
}
int q; cin >> q;
for(int i = 1; i <= q; ++i){
int u, v;
cin >> u >> v;
u = id[u], v = id[v];
++dp[u];
--dp[v];
}
for(int i = 1; i <= timerSCC; ++i){
if(!vst[i]){
dfsSolve(i, -1);
}
}
for(int i = 1; i <= m; ++i){
cout << c[ans[i]];
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
#define task "antuvu"
if(fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
Zero_OP();
return 0;
}
Compilation message
oneway.cpp: In function 'void dfsTarjan(int, int)':
oneway.cpp:37:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
37 | for(auto [id, dir] : g[u]) if(id != preID){
| ^
oneway.cpp: In function 'void dfsSolve(int, int)':
oneway.cpp:60:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
60 | for(auto [id, target] : G[u]) if(preID != id){
| ^
oneway.cpp: In function 'int main()':
oneway.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
121 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
122 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
