#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 2;
vector < pair < int , int > > edge;
vector < int > adj[N + 2];
stack < int > st;
vector < pair < int , int > > g[N + 2];
int f[N + 2];
int low[N + 2] , num[N + 2];
int timer = 0;
int scc = 0;
bool check[N * 2 + 2];
void add_edge(int u , int v){
adj[u].push_back(edge.size());
edge.push_back({u , v});
adj[v].push_back(edge.size());
edge.push_back({v , u});
}
void dfs(int u , int id_par = -1){
low[u] = num[u] = ++timer;
st.push(u);
for(auto id: adj[u]){
if(id_par != -1 && (id ^ id_par) == 1)continue;
int v = edge[id].second;
if(num[v]){
low[u] = min(low[u] , num[v]);
}
else{
dfs(v , id);
low[u] = min(low[u] , low[v]);
if(num[u] == low[v]){
scc++;
g[u].push_back({scc , -1});
g[scc].push_back({scc , -1});
int y;
while(y != v){
y = st.top();
st.pop();
g[y].push_back({scc , -1});
g[scc].push_back({y , -1});
}
}
if(num[u] < low[v]){
st.pop();
g[u].push_back({v , id});
g[v].push_back({u , (id ^ 1)});
}
}
}
}
void dfs2(int u , int id_par = -1 , int p = -1){
for(auto [v , id] : g[u]){
if(v == p) continue;
dfs2(v , id , u);
f[u] += f[v];
}
if(id_par == -1)return;
if(f[u] > 0){
check[id_par] = 1;
}
if(f[u] < 0){
check[id_par ^ 1] = 1;
}
}
void solve() {
int n , m;
cin >> n >> m;
scc = n;
for(int i = 1; i <= m ; i ++){
int u , v;
cin >> u >> v;
add_edge(u , v);
}
dfs(1);
int q;
cin >> q;
while(q -- ){
int u , v;
cin >> u >> v;
f[u] ++;
f[v] --;
}
dfs2(1);
for(int i = 0; i < m ;i ++){
if(check[i * 2]) cout << 'L';
else if(check[i * 2 + 1]) cout <<'R';
else{
cout << 'B';
}
}
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
#define _ "maxseq."
if (fopen(_ "inp", "r")) {
freopen(_ "inp", "r", stdin);
freopen(_ "out", "w", stdout);
}
solve();
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | freopen(_ "inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | freopen(_ "out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:38:25: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
38 | while(y != v){
| ~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
