#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;
class UnionFind {
public:
vi p;
vi r;
UnionFind(ll n){
p.resize(n);
r.resize(n,1);
rep(i,0,n) p[i] = i;
}
ll find(ll v){
return p[v]==v?v:p[v]=find(p[v]);
}
void join(ll a,ll b){
a = find(a); b = find(b);
if(r[a]>r[b]) p[b] = a;
else p[a] = b;
if(r[a]==r[b]) r[b]++;
}
};
ll n,m,p;
vector<vi> e;
vector<pii> ps;
vi dfsNum;
vi dfsLow;
vector<bool> in;
ll num = 0;
void findBridges(ll v, ll last){
if(dfsNum[v]!=-1) return;
dfsLow[v] = dfsNum[v] = num++;
random_shuffle(all(e[v]));
rep(i,0,e[v].size()){
if(e[v][i]==last) continue;
findBridges(e[v][i],v);
dfsLow[v] = min(dfsLow[v],dfsLow[e[v][i]]);
}
}
ll tn;
vector<vi> te;
vi addUp;
vi addDown;
map<pii,bool> isDown;
map<pii,bool> isUp;
class LCA {
public:
vector<vi> p;
vi level;
LCA(ll x){
p.resize(30,vi(tn));
level.resize(tn);
firstP(0,0,0);
rep(i,1,30)
rep(j,0,tn)
p[i][j] = p[i-1][p[i-1][j]];
}
void firstP(ll v, ll last, ll l){
p[0][v] = last;
level[v] = l;
rep(i,0,te[v].size()){
//cout<<v<<" "<<i<<endl;
if(te[v][i]!=last){
firstP(te[v][i],v,l+1);
}
}
}
ll getLca(ll a,ll b){
if(level[a]<level[b]) swap(a,b);
for(ll i = 29;i>=0;--i)
if(level[p[i][a]]>=level[b])
a = p[i][a];
if(a==b) return a;
for(ll i = 29;i>=0;--i)
if(p[i][a]!=p[i][b]){
a = p[i][a];
b = p[i][b];
}
assert(a!=b&&p[0][a]==p[0][b]);
return p[0][a];
}
};
pii findUpDown(ll v,ll l){
ll sumUp = addUp[v];
ll sumDown = addDown[v];
rep(i,0,te[v].size()){
if(te[v][i]!=l){
pii res = findUpDown(te[v][i],v);
sumUp += res.first;
sumDown += res.second;
}
}
if(sumUp>0) isUp[{v,l}] = true;
if(sumDown>0) isDown[{v,l}] = true;
return {sumUp,sumDown};
}
int main(){
cin.sync_with_stdio(false);
cin>>n>>m;
e.resize(n);
vector<pii> edgeList;
rep(i,0,m){
ll a,b;
cin>>a>>b;
--a; --b;
e[a].push_back(b);
e[b].push_back(a);
edgeList.emplace_back(a,b);
}
dfsNum.resize(n,-1);
dfsLow.resize(n);
findBridges(rand()%n,-1);
set<pii> bridges;
set<pii> notBridges;
rep(v,0,n){
rep(i,0,e[v].size()){
if(dfsNum[v]<dfsNum[e[v][i]]){
if(dfsNum[e[v][i]]==dfsLow[e[v][i]]){
bridges.emplace(min(ll(v),e[v][i]),max(ll(v),e[v][i]));
}else{
notBridges.emplace(min(ll(v),e[v][i]),max(ll(v),e[v][i]));
}
}
}
}
//cout<<endl;
//rep(i,0,bridges.size())
//cout<<bridges[i].first+1<<" "<<bridges[i].second+1<<endl;
UnionFind uf(n);
trav(edge,notBridges){
//rep(i,0,n) cout<<uf.find(i)<<" ";
//cout<<endl;
//cout<<notBridges[i].first<<"-"<<notBridges[i].second<<endl;
uf.join(edge.first,edge.second);
}
map<ll,vi> mGroups;
rep(i,0,n) mGroups[uf.find(i)].push_back(i);
vector<vi> groups;
vi groupIndex(n);
trav(g,mGroups){
rep(i,0,g.second.size()) groupIndex[g.second[i]] = groups.size();
//cout<<groups.size()<<": "<<g.second.size()<<endl;
groups.push_back(g.second);
}
tn = groups.size();
te.resize(tn);
trav(bridge,bridges){
ll a = groupIndex[bridge.first];
ll b = groupIndex[bridge.second];
te[a].push_back(b);
te[b].push_back(a);
//cout<<a<<" "<<b<<endl;
}
addUp.resize(tn);
addDown.resize(tn);
LCA lcaFinder(1);
cin>>p;
rep(i,0,p){
ll a,b;
cin>>a>>b;
a = groupIndex[a-1];
b = groupIndex[b-1];
addDown[a]++;
addUp[b]++;
ll l = lcaFinder.getLca(a,b);
addDown[l]--;
addUp[l]--;
}
/*rep(i,0,tn) cout<<addUp[i]<<" ";
cout<<endl;
rep(i,0,tn) cout<<addDown[i]<<" ";
cout<<endl;
*/
findUpDown(0,0);
/*
cout<<"up: "<<endl;
trav(a,isUp){
cout<<a.first.first<<" "<<a.first.second<<endl;
}
cout<<"down: "<<endl;
trav(a,isDown){
cout<<a.first.first<<" "<<a.first.second<<endl;
}*/
rep(i,0,m){
ll a = edgeList[i].first;
ll b = edgeList[i].second;
if(notBridges.find({min(a,b),max(a,b)})!=notBridges.end()){
cout<<"B";
continue;
}
a = groupIndex[a];
b = groupIndex[b];
if(lcaFinder.level[a]<lcaFinder.level[b]){
assert(!(isUp[{b,a}]&&isDown[{b,a}]));
if(isUp[{b,a}]) cout<<"R";
else if(isDown[{b,a}]) cout<<"L";
else cout<<"B";
} else {
assert(!(isUp[{a,b}]&&isDown[{a,b}]));
if(isUp[{a,b}]) cout<<"L";
else if(isDown[{a,b}]) cout<<"R";
else cout<<"B";
}
}
cout<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
