This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define fi first
#define se second
using namespace std;
const ll mod = 1e9 + 7;
const ll inf = 2e18;
const ll blocksz = 320;
const ll N = 1e5 + 8;
ll num[N],low[N],tdfs,m,n,q;
bool vst[N];
vpll adj[N];
bool bridge[N];
vpll edge = {{0,0}};
ll cnt_edge[N],cnt_vertex[N];
vi cc_vertex[N];
void dfs_bridge(ll u, ll p){
num[u] = low[u] = ++tdfs;
for(pll ed:adj[u]){
ll v = ed.fi, id = ed.se;
if(v == p) continue;
if(!num[v]){
dfs_bridge(v,u);
low[u] = min(low[u],low[v]);
if(low[v] == num[v]){
bridge[id] = 1;
}
}
else low[u] = min(low[u],num[v]);
}
}
ll cc[N],cntcc;
void dfs_component(ll u){
cc[u] = cntcc;
vst[u] = 1;
for(pll ed:adj[u]){
ll v = ed.fi, id = ed.se;
if(bridge[id]) continue;
if(vst[v]) continue;
dfs_component(v);
}
}
struct node{
ll v,id,x,y;
};
vector<node> g[N];
void build(){
for(ll i = 1; i <= n; i++) if(!num[i]) tdfs = 0, dfs_bridge(i,i);
for(ll i = 1; i <= n; i++) if(!vst[i]) cntcc++,dfs_component(i);
for(ll i = 1; i <= m; i++){
ll u = edge[i].fi, v = edge[i].se;
if(bridge[i]){
g[cc[u]].pb({cc[v],i,u,v});
g[cc[v]].pb({cc[u],i,v,u});
}
}
}
ll dp[N];
pll ans[N];
void direct(ll u, ll p){
vst[u] = 1;
for(node v:g[u]){
if(v.v == p) continue;
v.x = u, v.y = v.v;
direct(v.v,u);
}
}
void dfs(ll u, ll p) {
vst[u] = 1;
for(node v:g[u]){
if(v.v == p) continue;
dfs(v.v, u);
dp[u] += dp[v.v];
if(dp[v.v] > 0) ans[v.id] = {v.y, v.x};
if(dp[v.v] < 0) ans[v.id] = {v.x, v.y};
}
}
void solve(){
cin >> n >> m;
for(ll i = 1; i <= m; i++){
ans[i] = {-1,-1};
ll u,v;cin >> u >> v;
adj[u].pb({v,i});
adj[v].pb({u,i});
edge.pb({u,v});
}
build();
fill(vst,vst+n+1,0);
for(ll i = 1; i <= n; i++) if(!vst[i]) direct(i,i);
cin >> q;
while(q--){
ll u,v;cin >> u >> v;
dp[cc[u]]++;
dp[cc[v]]--;
}
fill(vst,vst+n+1,0);
for(ll i = 1; i <= n; i++) if(!vst[i]) dfs(i,i);
for(ll i = 1; i <= m; i++) {
if(ans[i].fi < 0 || !bridge[i]) cout << "B";
else cout << (ans[i] == edge[i] ? "R" : "L");
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen("test.inp", "r")){
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
ll T = 1;
// cin >> T;
for (ll i = 1; i <= T; i++){
solve();
cout << '\n';
}
}
Compilation message (stderr)
oneway.cpp: In function 'int main()':
oneway.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | freopen("test.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
120 | freopen("test.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |