// In the name of God
// Hope is last to die
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())
const int maxn = 1e5 + 5;
const int inf = 1e9 + 7;
int n, m, p, h[maxn], dp[maxn], sz[maxn], par[maxn], val[maxn];
vector<pair<int, pii>> adj[maxn], g[maxn];
pii ed[maxn];
char ans[maxn];
bool mark[maxn], cut[maxn];
int find(int u){
return u == par[u] ? u : par[u] = find(par[u]);
}
void merge(int u, int v){
u = find(u);
v = find(v);
if(u == v) return;
if(sz[u] > sz[v]) swap(u, v);
par[u] = v;
sz[v] += sz[u];
}
void dfs_cut(int v, int p){
dp[v] = h[v];
mark[v] = 1;
for(auto [u, e]: adj[v]){
if(p == e.F) continue;
if(!mark[u]){
h[u] = h[v] + 1;
dfs_cut(u, e.F);
if(dp[u] > h[v]) cut[e.F] = 1;
}
smin(dp[v], dp[u]);
}
}
void dfs(int v, int p = -1, int pe = -1, int d = -1){
mark[v] = 1;
for(auto [u, e]: g[v]){
if(u == p) continue;
dfs(u, v, e.F, e.S);
val[v] += val[u];
}
if(p == -1) return;
if(val[v] == 0){
ans[pe] = 'B';
return;
}
if(val[v] < 0){
if(d == 1) ans[pe] = 'R';
else ans[pe] = 'L';
}
else{
if(d == 0) ans[pe] = 'R';
else ans[pe] = 'L';
}
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++){
par[i] = i;
sz[i] = 1;
}
for(int i = 0; i < m; i++){
int u, v; cin >> u >> v;
adj[u].pb(mp(v, mp(i, 1)));
adj[v].pb(mp(u, mp(i, 0)));
ed[i] = mp(u, v);
}
dfs_cut(1, -1);
for(int i = 0; i < m; i++){
if(cut[i]) continue;
ans[i] = 'B';
merge(ed[i].F, ed[i].S);
}
for(int i = 0; i < m; i++){
if(!cut[i]) continue;
int v = find(ed[i].F), u = find(ed[i].S);
g[v].pb(mp(u, mp(i, 1)));
g[u].pb(mp(v, mp(i, 0)));
}
cin >> p;
for(int i = 0; i < p; i++){
int u, v; cin >> u >> v;
u = find(u), v = find(v);
val[u]++;
val[v]--;
}
fill(mark + 1, mark + n + 1, 0);
for(int i = 1; i <= n; i++){
if(!mark[find(i)]) dfs(find(i));
}
for(int i = 0; i < m; i++) cout << ans[i];
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
