#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=1e5+500;
const ll inf=1e9+800;
vector<ll> tree[maxn];
ll s[maxn];
ll t[maxn];
ll d[maxn];
ll pare[maxn];
bool vis[maxn];
void dfs2(ll a,ll p=-1){
vis[a]=1;
for(auto e:tree[a]){
ll v=(s[e]^t[e]^a);
if(v!=p){
dfs2(v,a);
d[a]+=d[v];
}else{
pare[a]=e;
}
}
}
ll st[maxn];
ll et[maxn];
ll tt=0;
vector<ll> ger[maxn];
bool boreshi[maxn];
ll h[maxn];
ll dp[maxn];
ll par[maxn];
char ans[maxn];
ll findPar(ll a){
if(par[a]==a)return a;
par[a]=findPar(par[a]);
return par[a];
}
void dfs(ll a,ll pe=-1){
vis[a]=1;
dp[a]=h[a];
for(auto e:ger[a]){
if(e!=pe){
ll v=(a^s[e]^t[e]);
if(!vis[v]){
h[v]=h[a]+1;
dfs(v,e);
if(dp[v]==h[v]){
boreshi[e]=1;
}
dp[a]=min(dp[a],dp[v]);
}else{
dp[a]=min(dp[a],h[v]);
}
}
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n,m;
cin>>n>>m;
for(ll i=0;i<m;i++){
cin>>s[i]>>t[i];
s[i]--;t[i]--;
ger[s[i]].pb(i);
ger[t[i]].pb(i);
}
for(ll i=0;i<n;i++){
if(vis[i]==0){
dfs(0);
}
}
for(ll i=0;i<n;i++){
par[i]=i;
}
for(ll i=0;i<m;i++){
if(!boreshi[i]){
ll x=findPar(s[i]);
ll y=findPar(t[i]);
if(x!=y){
par[x]=y;
}
ans[i]='B';
}
}
for(ll i=0;i<m;i++){
if(boreshi[i]){
s[i]=findPar(s[i]);
t[i]=findPar(t[i]);
tree[s[i]].pb(i);
tree[t[i]].pb(i);
}
}
memset(vis,0,sizeof vis);
ll p;
cin>>p;
for(ll i=0;i<p;i++){
ll x,y;
cin>>x>>y;
x--;y--;
x=findPar(x);
y=findPar(y);
d[x]++;
d[y]--;
}
fill(pare,pare+maxn,-1);
for(ll i=0;i<n;i++){
if(par[i]==i && !vis[i]){
dfs2(i);
}
}
for(ll i=0;i<n;i++){
if(par[i]==i){
if(pare[i]>=0){
if(d[i]==0){
ans[pare[i]]='B';
}else{
if(s[pare[i]]==i){
ans[pare[i]]='R';
}else{
ans[pare[i]]='L';
}
if(d[i]<0){
if(ans[pare[i]]=='L')ans[pare[i]]='R';
else ans[pare[i]]='L';
}
}
}
}
}
for(ll i=0;i<m;i++){
cout<<ans[i];
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
