#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define debug if(0)
const int N = 1e5 + 10;
vector<pair<int, int>> V[N], W[N];
vector<int> comp;
int low[N], no[N], de[N], val[N], c[N], T = 0, X = 0;
bool vis[N], bridge[N];
void dfs(int v, int eid=0) {
vis[v] = 1;
no[v] = T++;
low[v] = no[v];
for(auto e : V[v]) {
int u = e.first, id = e.second;
if(id == eid) continue;
if(!vis[u]) {
dfs(u, id);
low[v] = min(low[v], low[u]);
}
else low[v] = min(low[v], no[u]);
if(low[u] > no[v]) bridge[id] = 1;
}
}
void dfs2(int v) {
vis[v] = 1;
c[v] = X;
for(auto e : V[v]) {
int u = e.first, id = e.second;
if(bridge[id]) continue;
if(!vis[u]) dfs2(u);
}
}
void dfs3(int v) {
vis[v] = 1;
for(auto e : W[v]) {
int u = e.first, id = e.second;
if(!vis[u]) {
if(val[u] > val[v]) de[id] = 1;
else if(val[u] < val[v]) de[id] = 2;
dfs3(u);
}
}
}
void clear(int n) {
for(int i=0; i<=n; i++) vis[i] = 0;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, p; cin>>n>>m;
for(int i=0; i<m; i++) {
int a, b; cin>>a>>b;
V[a].push_back({b, i});
V[b].push_back({a, i});
}
for(int i=1; i<=n; i++) {
if(!vis[i]) dfs(i);
}
clear(n);
for(int i=1; i<=n; i++) {
if(!vis[i]) {
X++;
dfs2(i);
}
}
for(int i=1; i<=n; i++) {
for(auto e : V[i]) {
int u = e.first, id = e.second;
if(c[i] != c[u]) W[c[i]].push_back({c[u], id});
}
}
clear(n);
cin>>p;
for(int i=0; i<p; i++) {
int a, b; cin>>a>>b;
if(c[a] == c[b]) continue;
val[c[a]]--;
val[c[b]]++;
}
for(int i=1; i<=n; i++) {
if(!vis[i]) dfs3(i);
}
for(int i=0; i<m; i++) {
if(de[i] == 1) cout<<"R";
else if(de[i] == 2) cout<<"L";
else cout<<"B";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
