#include <bits/stdc++.h>
#define z exit(0)
#define mp make_pair
#define F first
#define S second
using namespace std;
using pii = pair<int,int>;
const int N = 100000;
vector<int> g[N], tree[N], st[N], ed[N];
set<pii> bridge, ok;
map<pii,int> cnt;
int tin[N], low[N], rt[N], up[N], ti, sz;
set<int> ds;
pii I[N];
void dfs(int u, int p){
low[u] = tin[u] = ti++;
for(int v: g[u]){
if(v != p){
if(tin[v] == -1){
tree[u].push_back(v);
dfs(v, u);
low[u] = min(low[u], low[v]);
int x = min(u, v), y = max(u, v);
if(low[v] > tin[u] && cnt[mp(x, y)] == 1){
bridge.emplace(x, y);
}
}else{
low[u] = min(low[u], tin[v]);
}
}
}
}
void efs(int u){
for(int v: tree[u]) up[v] = u, efs(v);
for(int i: st[u]) ds.insert(i);
for(int i: ed[u]) if(ds.find(i) != ds.end()) ds.erase(i);
if(up[u] != -1 && !ds.empty()) ok.emplace(up[u], u);
}
signed main(){
int n, m; scanf("%d %d", &n, &m);
for(int i = 0, u, v; i<m; ++i){
scanf("%d %d", &u, &v); --u; --v;
I[i] = {u, v};
if(u > v) swap(u, v);
if(!cnt[mp(u, v)]){
g[u].push_back(v); g[v].push_back(u);
}
++cnt[mp(u, v)];
}
memset(tin, -1, sizeof(tin));
for(int i = 0; i<n; ++i){
if(tin[i] == -1) dfs(rt[sz++] = i, -1);
}
int q; scanf("%d", &q);
for(int i = 0, u, v; i<q; ++i){
scanf("%d %d", &u, &v); --u; --v;
st[u].push_back(i); ed[v].push_back(i);
}
memset(up, -1, sizeof(up));
for(int i = 0; i<sz; ++i) efs(rt[i]);
for(int i = 0; i<m; ++i){
int u = I[i].F, v = I[i].S;
if(bridge.find(mp(min(u, v), max(u, v))) == bridge.end()){
printf("B"); continue;
}
char ch;
if(u == up[v]){
ch = 'R';
if(ok.find(mp(u, v)) != ok.end()) ch = 'L';
}else if(v == up[u]){
ch = 'L';
if(ok.find(mp(v, u)) != ok.end()) ch = 'R';
}
printf("%c", ch);
}
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:40:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | int n, m; scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | scanf("%d %d", &u, &v); --u; --v;
| ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | int q; scanf("%d", &q);
| ~~~~~^~~~~~~~~~
oneway.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d %d", &u, &v); --u; --v;
| ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:74:9: warning: 'ch' may be used uninitialized in this function [-Wmaybe-uninitialized]
74 | printf("%c", ch);
| ~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
11856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
11856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
11856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
