#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 100;
const int MAX_LOG = 18;
vector<pair<int, int>> a[MAXN];
vector<pair<int, int>> bridges[MAXN];
vector<pair<int, int>> edges;
int parent[MAXN][MAX_LOG];
int tin[MAXN];
int tout[MAXN];
int components = 0;
int counter = 0;
int bridge = 0;
int num[MAXN];
int low[MAXN];
bool isBridge[MAXN];
int vis[MAXN];
int comp[MAXN];
int cnt[MAXN];
int ans[MAXN];
int inv[MAXN];
int n, m, p;
void dfs(int u, int p, int f){
num[u] = low[u] = ++counter;
for (auto x: a[u]){
int v = x.first;
if (x.second == f) continue;
if (!num[v]){
dfs(v, u, x.second);
low[u] = min(low[u], low[v]);
if (low[v] == num[v]){
bridge++;
isBridge[x.second] = true;
}
}
else low[u] = min(low[u], num[v]);
}
}
void dfs1(int u, int p){
comp[u] = components;
vis[u] = 1;
for (auto v: a[u]){
if (vis[v.first] || isBridge[v.second]) continue;
dfs1(v.first, u);
}
}
void dfs2(int u, int p){
parent[u][0] = p;
vis[u] = 1;
for (auto x: bridges[u]){
int v = x.first;
if (v != p){
//inv[x.second] = (u != comp[edges[x.second].first]);
dfs2(v, u);
}
}
}
void pre(){
counter = 0;
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= components; i++){
if (!vis[i]) dfs2(i, i);
}
}
void dfs3(int u, int p){
vis[u] = 1;
for (auto x: bridges[u]){
int v = x.first;
if (v == p) continue;
dfs3(v, u);
cnt[u] += cnt[v];
if (cnt[v] > 0){
ans[x.second] = 1;
}
else if (cnt[v] < 0){
ans[x.second] = -1;
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++){
int x, y;
cin >> x >> y;
a[x].push_back({y, i});
a[y].push_back({x, i});
edges.push_back({x, y});
}
counter = 0;
for (int i = 1; i <= n; i++){
if (!num[i]){
dfs(i, -1, -1);
}
}
for (int i = 1; i <= n; i++){
if (!vis[i]){
components++;
dfs1(i, -1);
}
}
for (int i = 0; i < m; i++){
if (isBridge[i]){
bridges[comp[edges[i].first]].push_back({comp[edges[i].second], i});
bridges[comp[edges[i].second]].push_back({comp[edges[i].first], i});
}
}
pre();
cin >> p;
while (p--){
int x, y;
cin >> x >> y;
x = comp[x];
y = comp[y];
cnt[x]++;
cnt[y]--;
}
memset(vis,0 ,sizeof(vis));
for (int i = 1; i <= components; i++){
if (!vis[i]) dfs3(i, -1);
}
for (int i = 0; i < m; i++){
if (inv[i]) ans[i] *= (-1);
if (ans[i] == -1) cout << "R";
else if (ans[i] == 1) cout << "L";
else cout << "B";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
5468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
5468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
5468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
