#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pii pair<int,int>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define f first
#define int long long
#define s second
#define pii pair<int,int>
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
const int N=3e5 + 5 ;
const int inf = 1e17 + 7;
const int mod = 998244353;
map<pii,int>e_cnt,edge,mp;
vector<int>g[N],vis(N),tin(N),fup(N),color(N),A(N),B(N),ans(N);
vector<pii>v[N],nw;
int n,m,k, timer;
void bridge(int x, int p = -1){
vis[x] = 1;
tin[x] = ++timer;
fup[x] = ++timer;
for(auto to:g[x]){
if(to == p)continue;
if(vis[to]){
umin(fup[x],fup[to]);
}
else{
bridge(to);
umin(fup[x],fup[to]);
if(fup[to]>tin[x]){
mp[{x,to}] = 1;
mp[{to,x}] = 1;
}
}
}
}
void dfs(int x, int col){
vis[x] = 1;
color[x] = col;
for(auto to:g[x]){
if(vis[to])continue;
if(mp[{x,to}] != 1 || e_cnt[{to,x}] > 1)
dfs(to,col);
}
}
void DFS(int x, int p){
vis[x] = 1;
for(auto [to,ind]:v[x]){
if(to == p)continue;
DFS(to,x);
A[x] += A[to];
B[x] += B[to];
}
for(auto [to,ind]:v[x]){
if(to == p) continue;
if(A[to] != B[to]){
if(ind < 0)
ans[-ind]=1;
else
ans[ind]=0;
if(B[to]>A[to]) ans[abs(ind )]^=1;
}
}
}
int c = 1;
void magic_nahuy(){
int op;cin >> op;
for(int i = 1;i<=m;i++){
ans[i] = 2;
vis[i] = 0;
}
for(int i = 0;i<op;i++){
int a,b;
cin >> a >> b;
A[color[a]] += 1;
B[color[b]] += 1;
}
for(int i = 1;i<=c;i++){
if(vis[i])continue;
DFS(i,-1);
}
for(int i = 1;i<=m;i++){
if(ans[i] == 2)cout<<"B";
if(ans[i] == 1)cout<<"R";
if(ans[i] == 0)cout<<"L";
}
}
void solve(){
cin >> n >> m;
for(int i = 1; i<=m ;i++){
int a,b;
cin >> a >> b;
e_cnt[{a,b}] += 1;
e_cnt[{b,a}] += 1;
g[a].pb(b);
g[b].pb(a);
edge[{a,b}] = i;
edge[{b,a}] = -i;
nw.pb({a,b});
}
for(int i = 1;i<=n;i++){
if(vis[i])continue;
bridge(i);
}
for(int i = 1;i<=n;i++){
vis[i] = 0;
}
for(int i = 1;i<=n;i++){
if(vis[i])continue;
dfs(i,c++);
}
for(auto it:nw){
if(color[it.f] == color[it.s])continue;
v[color[it.f]].pb({color[it.s],edge[it]});
v[color[it.s]].pb({color[it.f],-edge[it]});
}
magic_nahuy();
}
signed main()
{
// freopen("seq.in", "r", stdin);
// freopen("seq.out", "w", stdout);
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int tt=1;//cin>>tt>>n;
while(tt--)solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
30808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
30808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
30808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
