#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<PP> vpp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(v) v.begin(),v.end()
#define dupli(v) {sort(all(v));v.erase(unique(all(v)),v.end());}
#define rsort(a) {sort(all(a));reverse(all(a));}
#define pb emplace_back
#define fi first
#define se second
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T>void out(T a){cout<<a<<endl;}
template<class T>void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<endl;}
template<class T>void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T>void outvp(T v){for(auto a:v)cout<<'('<<a.fi<<','<<a.se<<')';cout<<endl;}
template<class T>void outvv(T v){for(auto x:v)outv(x);}
template<class T>void outvvp(T v){for(auto x:v)outvp(x);}
const ll inf=1001001001001001001;
class UF{
vi sz,par;
public:
UF(ll n){
sz=vi(n,1);rep(i,n)par.pb(i);
}
ll root(int i){
if(par[i]==i)return i;
return root(par[i]);
}
void merge(int a,int b){
a=root(a);b=root(b);
if(a==b)return;
if(sz[a]>sz[b])swap(a,b);
par[a]=b;
sz[b]+=sz[a];
}
};
int main(){
ll n,m;cin>>n>>m;
vvp g(n);
vb rev(m,false);
rep(i,m){
ll a,b;cin>>a>>b;a--;b--;
g[a].pb(b,i);g[b].pb(a,-i-1);
}
vi ans(m),dep(n,-1),lk(n,inf);
vp par(n,P(-1,-1));
UF uf(n);
function<void(ll,ll,ll)> dfs=[&](ll i,ll p,ll e){
for(P x:g[i])if(x.se!=e&&-1-x.se!=e){
if(dep[x.fi]==-1){
if(x.se<0){
x.se*=-1;x.se--;rev[x.se]=true;
}
dep[x.fi]=dep[i]+1;
dfs(x.fi,i,x.se);
chmin(lk[i],lk[x.fi]);
}
else{
if(x.se<0){
x.se*=-1;x.se--;
}
else rev[x.se]=true;
chmin(lk[i],dep[x.fi]);
}
}
if(lk[i]<dep[i])uf.merge(i,p);
else par[uf.root(i)]=P(p,e);
};
dep[0]=0;
dfs(0,-1,-1);
vvp tree(n);
rep(i,n)if(par[i].fi!=-1)tree[uf.root(par[i].fi)].pb(i,par[i].se);
vi cnt(n);
ll q;cin>>q;
rep(i,q){
ll a,b;cin>>a>>b;a--;b--;
cnt[uf.root(a)]++;cnt[uf.root(b)]--;
}
function<ll(ll,ll,ll)> add=[&](ll i,ll p,ll e){
for(auto x:tree[i])if(x.fi!=p)cnt[i]+=add(x.fi,i,x.se);
if(cnt[i]>0)ans[e]=1;
if(cnt[i]<0)ans[e]=-1;
return cnt[i];
};
add(uf.root(0),-1,-1);
rep(i,m)if(rev[i])ans[i]*=-1;
rep(i,m){
if(ans[i]==-1)cout<<'R';
if(ans[i]==0)cout<<'B';
if(ans[i]==1)cout<<'L';
}cout<<endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
