#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
const ll lim=1e5+5;
ll n,m,q;
vector<char>ans;
struct UFDS{
ll par[lim];
UFDS(){
for(int i=0;i<lim;i++)par[i]=i;
}
ll findset(ll pos){
if(pos==par[pos])return pos;
else return par[pos]=findset(par[pos]);
}
void mergeset(ll a,ll b){
a = findset(a),b = findset(b);
if(a!=b)par[b]=a;
}
}ufds;
struct Edge{
ll x,a,b,idx;//x is the other guy, a and b are original order of edge
Edge(ll xx,ll aa,ll bb,ll ii){
x=xx,a=aa,b=bb,idx=ii;
}
Edge(){}
};
struct Graph{
vector<Edge>adjl[lim],nontree;
ll par[lim],depth[lim];
Edge paredge[lim];
bool vis[lim],root[lim];
Graph(){
fill(vis,vis+lim,0);
fill(root,root+lim,0);
fill(depth,depth+lim,0);
par[1]=1;
depth[1]=0;
}
void dfs(ll pos,ll pre_idx){
vis[pos]=1;
//cout<<"pos:"<<pos<<"\n";
for(Edge &E:adjl[pos]){
if(E.idx==pre_idx){
swap(E,adjl[pos].back());
adjl[pos].pop_back();
break;
}
}
for(Edge E:adjl[pos]){
if(!vis[E.x]){
vis[E.x]=1;
par[E.x]=pos;
paredge[E.x]=E;
depth[E.x]=depth[pos]+1;
dfs(E.x,E.idx);
}
else if(pos<E.x){ //prevent duplication (each extra edge goes into nontree once only)
// cout<<"pos eidx:"<<pos<<" "<<E.idx<<"\n";
nontree.push_back(E);
}
}
return;
}
void roottrees(){
for(int i=1;i<=n;i++){
if(vis[i]==0)dfs(i,-1),root[i]=1;
}
}
//Part 1, processing the nontree edges
void proc(Edge E){//marks a cycle in the tree
ll ha=ufds.findset(E.a),hb=ufds.findset(E.b);
while(ha!=hb){
if(depth[ha]<depth[hb])swap(ha,hb);
ufds.mergeset(par[ha],ha);
ans[paredge[ha].idx]='B';
ha=ufds.findset(par[ha]);
}
return;
}
void genH(){
for(auto E:nontree){
ans[E.idx]='B';
proc(E);
}
return;
for(int i=1;i<=n;i++){
if(root[i]){
// cout<<i<<" is a root\n";
continue;
}
if(ufds.findset(i)==i){
// cout<<i<<" is a head\n";
// H->adjl[ufds.findset(par[i])].push_back(paredge[i]);
// cout<<ufds.findset(par[i])<<" "<<(i)<<"\n";
// cout<<"Edge:"<<paredge[i].a<<" "<<paredge[i].b<<"\n\n";
}
}
return;
}
//Part 2, answering the queries
void query(ll a,ll b){
ll ha=ufds.findset(a),hb=ufds.findset(b);
while(ha!=hb){
if(depth[ha]>depth[hb]){
ll nxt=ufds.findset(par[ha]);
ufds.mergeset(nxt,ha);
Edge E=paredge[ha];
assert((E.a==ha)^(E.b==ha));
ans[E.idx]= (E.a==ha)?'R':'L';
ha=nxt;
}
else{
ll nxt=ufds.findset(par[hb]);
ufds.mergeset(nxt,hb);
Edge E=paredge[hb];
assert((E.a==ha)^(E.b==ha));
ans[E.idx]= (E.a==hb)?'L':'R';
hb=nxt;
}
}
return;
}
};
int main(){
ios_base::sync_with_stdio(0),cin.tie(NULL);
cin>>n>>m;
ans=vector<char>(m,'B');
Graph G;
for(int i=0;i<m;i++){
ll a,b;
cin>>a>>b;
if(a==b){
ans[i]='B';
continue;
}
G.adjl[a].push_back(Edge(b,a,b,i));
G.adjl[b].push_back(Edge(a,a,b,i));
}
G.roottrees();
G.genH();
cin>>q;
while(q--){
ll a,b;
cin>>a>>b;
G.query(a,b);
}
// for(auto x:G.nontree){
// cout<<x.a<<" "<<x.b<<" "<<x.idx<<"\n";
// }
for(auto c:ans)cout<<c;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
16716 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
16716 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
16716 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
