#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
vector <vector<ar<int,2>>> adj(n);
for ( int i = 0; i < m; i++ ){
int u, v; cin >> u >> v;
--u, --v;
adj[u].pb({v, i});
adj[v].pb({u, i});
}
int p; cin >> p;
vector <vector<ar<int,2>>> q(n);
for ( int i = 0; i < p; i++ ){
int x, y; cin >> x >> y;
--x, --y;
q[x].pb({y, 0});
q[y].pb({x, 1});
}
vector <int> us(n), tin(n), tout(n);
int ct = -1;
auto trav = [&](auto trav, int u, int p) -> void{
us[u] = true;
tin[u] = ++ct;
for ( auto &[v, j]: adj[u] ){
if ( v != p && !us[v] ){
trav(trav, v, u);
}
} tout[u] = ct;
};
vector <int> roots;
for ( int i = 0; i < n; i++ ){
if ( !us[i] ){
roots.pb(i);
trav(trav, i, -1);
}
}
vector <int> low(n), ans(m, -1);
vector <pair<int,int>> mn(n), mx(n);
auto dfs = [&](auto dfs, int u, int p) -> void{
mn[u] = {n, -1};
mx[u] = {-1, -1};
for ( auto &[v, t]: q[u] ){
chmin(mn[u], pair<int,int>{tin[v], t});
chmax(mx[u], pair<int,int>{tout[v], t});
}
low[u] = tin[u];
vector <ar<int,2>> tmp;
for ( auto &[v, j]: adj[u] ){
if ( v != p ){
if ( low[v] ){
chmin(low[u], tin[v]);
} else{
dfs(dfs, v, u);
chmin(mn[u], mn[v]);
chmax(mx[u], mx[v]);
chmin(low[u], low[v]);
if ( low[v] > tin[u] ){
tmp.pb({v, j});
}
}
}
}
for ( auto &[v, j]: tmp ){
if ( mn[v].first < tin[v] ){
ans[j] = mn[v].second;
}
if ( mx[v].first > tout[v] ){
ans[j] = mx[v].second;
}
}
};
for ( auto &u: roots ){
dfs(dfs, u, -1);
}
for ( auto &x: ans ){
cout << (x > 0 ? 'L' : x < 0 ? 'B' : 'R');
}
// cout << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
