#include<bits/stdc++.h>
using namespace std;
set<pair<int, int>> edges;
map<pair<int, int>, int> f;
map<pair<int, int>, pair<int, int>> edge_tree_to_graph;
vector<pair<int, int>> bridges;
vector<int> ad[100005], ad2[100005];
int low[100005], num[100005], c[100005], dp[100005], ans[100005], dfsc = 0, color = 0;
//0 = B; 1 = L; 2 = R;
bool visited[100005];
inline pair<int, int> edgeCorrection(pair<int, int> x)
{
if(edges.count(x) == 0) swap(x.first, x.second);
return x;
}
void dfs(int u, int par)
{
low[u] = num[u] = ++dfsc;
bool avoidpar = 1;
for(int v : ad[u]){
if(v != par || avoidpar == 0){
if(num[v] > 0) low[u] = min(low[u], num[v]);
else{
dfs(v, u);
low[u] = min(low[u], low[v]);
}
}
else avoidpar = 0;
}
}
void dfscolor(int u)
{
visited[u] = 1; c[u] = color;
for(int v : ad[u]) if(visited[v] == 0){
if(low[v] == num[v]){
color++;
bridges.push_back(edgeCorrection({u, v}));
}
dfscolor(v);
}
}
void dfsdirect(int u)
{
visited[u] = 1;
for(int v : ad2[u]) if(visited[v] == 0){
dfsdirect(v); dp[u] += dp[v];
if(dp[v] != 0){
pair<int, int> thisedge = edge_tree_to_graph[{u, v}];
if(dp[v] > 0){
if(c[thisedge.first] == u) ans[f[thisedge]] = 1;
else ans[f[thisedge]] = 2;
}
else{
if(c[thisedge.first] == u) ans[f[thisedge]] = 2;
else ans[f[thisedge]] = 1;
}
}
}
//cout<<u<<" "<<dp[u]<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin>>n>>m;
for(int i = 1; i <= m; i++){
int u, v;
cin>>u>>v;
if(u == v) continue;
ad[u].push_back(v);
ad[v].push_back(u);
edges.insert({u, v});
f[{u, v}] = i;
}
for(int i = 1; i <= n; i++) if(num[i] == 0){
dfs(i, -1);
color++;
dfscolor(i);
}
for(pair<int, int> i : bridges){
ad2[c[i.first]].push_back(c[i.second]);
ad2[c[i.second]].push_back(c[i.first]);
edge_tree_to_graph[{c[i.first], c[i.second]}] = i;
edge_tree_to_graph[{c[i.second], c[i.first]}] = i;
}
int p; cin>>p;
for(int i = 1; i <= p; i++){
int u, v;
cin>>u>>v;
dp[c[u]]++; dp[c[v]]--;
}
//cout<<"A"<<color<<" "<<bridges.size()<<endl;
memset(visited, 0, sizeof(visited));
for(int i = 1; i <= color; i++) if(visited[i] == 0){
dfsdirect(i);
}
for(int i = 1; i <= m; i++){
if(ans[i] == 0) cout<<"B";
else if(ans[i] == 1) cout<<"L";
else cout<<"R";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
7004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
7004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
7004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
