// __builtin_popcount(x)
// __builtin_popcountll(x)
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
#define maxn 100005
ll n,m;
map<pll,ll> cnt;
map<pll,bool> ans;
ll con[maxn];
vector<ll> g[maxn];
ll in[maxn];
vector<pll> edge;
ll it = 1;
ll low[maxn];
bool vis[maxn];
stack<ll> stk;
map<pll,bool> bio;
map<pll,bool> most;
ll dsu[maxn];
ll comp = 1;
void dfs(ll u,ll par){
low[u] = in[u] = it++;
vis[u] = 1;
stk.push(u);
for(ll s : g[u]){
if(s==par){
if(cnt[{u,par}]==1) continue;
low[u] = min(low[u],low[s]);
continue;
}
if(!vis[s]) dfs(s,u);
low[u] = min(low[u],low[s]);
}
if(u==par) return;
if(low[u]>low[par]){
most[{u,par}] = 1;
most[{par,u}] = 1;
}
}
void dfs4(ll u,ll par){
vis[u] = 1;
dsu[u] =comp;
for(ll s : g[u]){
if(s==par) continue;
if(most[{u,s}]) continue;
if(vis[s]) continue;
dfs4(s,u);
}
}
ll root(ll x){
while(x!=con[x]){
con[x] = con[con[x]];
x = con[x];
}
return x;
}
void upd(ll x,ll y){
x = root(x);
y = root(y);
con[x] = con[y];
}
ll q;
#define lg 25
ll in2[maxn];
ll out2[maxn];
vector<ll> v[maxn];
ll st[maxn][lg];
void dfs2(ll u,ll par){
vis[u] =1;
st[u][0] = par;
in2[u] = it++;
for(ll s : v[u]){
if(s==par) continue;
dfs2(s,u);
}
out2[u] = it-1;
}
bool intree(ll x,ll y){
return in2[x]>=in2[y]&&out2[y]>=out2[x];
}
ll lca(ll x,ll y){
if(intree(x,y)) return y;
if(intree(y,x)) return x;
for(ll j = lg-1;j>=0;j--){
if(!intree(x,st[y][j])) y = st[y][j];
}
return st[y][0];
}
map<pll,ll> mp;
ll poc[maxn];
ll kr[maxn];
void dfs3(ll u,ll par){
vis[u] =1;
for(ll s : v[u]){
if(s==par) continue;
dfs3(s,u);
poc[u]+=poc[s];
kr[u]+=kr[s];
}
mp[{u,par}] = poc[u]-kr[u];
mp[{par,u}] = poc[u]-kr[u];
}
map<pll,pll> tru;
int main(){
ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
cin >> n >> m;
for(ll i = 1;i<=m;i++){
ll x,y; cin >> x >> y;
cnt[{x,y}]++;
cnt[{y,x}]++;
edge.pb({x,y});
g[x].pb(y);
g[y].pb(x);
}
dfs(1,1);
fill(vis,vis+n+1,0);
for(ll i = 1;i<=n;i++) if(vis[i]==0){dfs4(i,i);comp++;}
for(ll i = 1;i<=n;i++) if(dsu[i] == 0) dsu[i] = comp;
iota(con+1,con+n+1,1);
for(pll p : edge){
ll x = p.fi;
ll y = p.sc;
if(root(dsu[x])==root(dsu[y])) continue;
tru[{x,y}] = {dsu[x],dsu[y]};
tru[{y,x}] = {dsu[x],dsu[y]};
tru[{y,x}] = {dsu[y],dsu[x]};
tru[{x,y}] = {dsu[y],dsu[x]};
v[dsu[x]].pb(dsu[y]);
v[dsu[y]].pb(dsu[x]);
upd(dsu[x],dsu[y]);
}
it = 1;
fill(vis,vis+n+1,0);
for(ll i = 1;i<=n;i++) if(vis[i]==0) dfs2(i,i);
for(ll j = 1;j<lg;j++) for(ll i = 1;i<=n;i++) st[i][j] = st[st[i][j-1]][j-1];
cin >> q;
bool moe = 1;
for(ll i = 1;i<=q;i++){
ll x,y; cin >> x >> y;
x = dsu[x];
y = dsu[y];
if(x==y) continue;
if(st[x][lg-1]!=st[y][lg-1]) moe = 0;
poc[x]++;
kr[y]++;
ll z = lca(x,y);
poc[z]--;
kr[z]--;
//cerr<<"lca: "<<x<< " "<<y<< " "<<z<<endl;
}
//here;
//cerr<<"DSU: "<<endl;
//ceri(dsu,1,n);
fill(vis,vis+n+1,0);
//for(ll i = 1;i<=n;i++) cerr<<poc[i]-kr[i]<<" ";
//cerr<<endl;
for(ll i = 1;i<=n;i++) if(vis[i]==0) dfs3(i,i);
//for(ll i = 1;i<=n;i++) cerr<<poc[i]-kr[i]<<" ";
//cerr<<endl;
for(pll p : edge){
if(p.fi==p.sc){
cout<<'B';
continue;
}
if(cnt[p]>1) cout<<'B';
else{
if(dsu[p.fi]==dsu[p.sc]){
cout<<'B';
continue;
}
ll x = mp[tru[p]];
if(x==0) cout<<'B';
else if(x>0){
if(in2[dsu[p.fi]]>in2[dsu[p.sc]]) cout<<'R';
else cout<<'L';
}else{
if(in2[dsu[p.fi]]>in2[dsu[p.sc]]) cout<<'L';
else cout<<'R';
}
}
}
cout<<endl;
return 0;
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:155:10: warning: variable 'moe' set but not used [-Wunused-but-set-variable]
155 | bool moe = 1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
