#ifndef Local
#pragma GCC optimize("O3,unroll-loops")
#endif
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define int int64_t
const int lim=1e5+100;
int mod=998244353;
//const int mod=(1ll<<61)-1;
using pii=pair<int,int>;
bool isbridge[lim];
int tin[lim],tt=1;
vector<pii>v[lim];
int dfs(int node,int camefrom=lim-1){
tin[node]=tt++;
int seen=INT_MAX;
for(int j=0;j<size(v[node]);j++){
if(v[node][j].second^camefrom){
if(!tin[v[node][j].first]){
seen=min(seen,dfs(v[node][j].first,v[node][j].second));
}else{
seen=min(seen,tin[v[node][j].first]);
}
}
}
//cerr<<node<<" "<<tin[node]<<" "<<seen<<"\n";
if(tin[node]<=seen){
isbridge[camefrom]=1;
}
return seen;
}
int comp[lim],cnt=1;
void groupall(int node){
comp[node]=cnt;
for(int j=0;j<size(v[node]);j++){
if(!comp[v[node][j].first]&&!isbridge[v[node][j].second]){
groupall(v[node][j].first);
}
}
}
vector<pii>to[lim];
vector<pii>edges;
int vals[lim];
char ans[lim];
int compdfs(int node,int camefrom=lim-1){
//cerr<<node<<" "<<camefrom<<" visiting\n";
for(auto[j,i]:to[node]){
if(i^camefrom){
vals[node]+=compdfs(j,i);
}
}
if(0<vals[node]){
ans[camefrom]=(node==comp[edges[camefrom].first])?'R':'L';
}
if(vals[node]<0){
ans[camefrom]=(node==comp[edges[camefrom].first])?'L':'R';
}
//cerr<<node<<" "<<vals[node]<<"\n";
return vals[node];
}
void solve(){
int n,m;
cin>>n>>m;
edges.pb({0,0});
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
v[x].pb({y,i});
v[y].pb({x,i});
edges.pb({x,y});
//cerr<<i<<" | "<<x<<" "<<y<<"\n";
}
for(int i=1;i<=n;i++){
if(!tin[i]){
dfs(i);
}
}
for(int i=1;i<=n;i++){
if(!comp[i]){
groupall(i);
cnt++;
}
}
for(int i=1;i<=m;i++){
if(isbridge[i]){
//cerr<<i<<"\n";
//cerr<<i<<" | "<<edges[i].first<<" "<<edges[i].second<<" | new bridge\n";
to[comp[edges[i].first]].pb({comp[edges[i].second],i});
to[comp[edges[i].second]].pb({comp[edges[i].first],i});
}
}
//cerr<<"ok\n";
for(int i=1;i<=m;i++){
ans[i]='B';
}
/*
for(int i=1;i<=n;i++){
cerr<<comp[i]<<" ";
}cerr<<"\n";
for(int i=1;i<=cnt;i++){
cerr<<i<<" :\n";
for(auto[j,c]:to[i]){
cerr<<j<<" "<<c<<"\n";
}cerr<<"\n";
}
*/
int q;
cin>>q;
for(int i=0;i<q;i++){
int x,y;
cin>>x>>y;
int aa=comp[x],bb=comp[y];
vals[aa]++,vals[bb]--;
}
compdfs(1);
for(int i=1;i<=m;i++){
cout<<ans[i];
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
#ifdef Local
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
int t=1;
//cin>>t;
while (t--)
{
solve();
}
}
Compilation message
oneway.cpp: In function 'int64_t dfs(int64_t, int64_t)':
oneway.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(int j=0;j<size(v[node]);j++){
| ~^~~~~~~~~~~~~~
oneway.cpp: In function 'void groupall(int64_t)':
oneway.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int j=0;j<size(v[node]);j++){
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
