#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 1e5+100;
int idx[nax],low[nax],T,gid[nax],cmp,d[nax],to[nax];
int par[nax][22],be[nax];
vector<pair<int,int>> l[nax],g[nax];
vector<int> s;
bool vis[nax],isbridge[nax];
int u[nax],v[nax];
char ans[nax];
int lvl[nax],dp[nax];
void findbridges(int u,int p = 0,int e = 0){
dp[u] = 0;
for(pair<int,int> cur : g[u]){
int v = cur.first;
e = cur.second;
if(lvl[v] == 0){//span edge
lvl[v] = lvl[u] + 1;
findbridges(v,u,e);
dp[u] += dp[v];
}else if(lvl[v] > lvl[u]){//edges downwards
dp[u]--;
}else if(lvl[v] < lvl[u]){//edges upwards
dp[u]++;
}
}
dp[u]--; // We dont count the edge from p to u
if(lvl[u] > 1 && dp[u] == 0){//edge between u and its parent is a bridge
isbridge[e] = 1;
}
}
void getscc(int u){
vis[u]=1;
gid[u] = cmp;
for(int i=0;i<g[u].size();i++){
int v = g[u][i].first;
int e = g[u][i].second;
if(isbridge[e])continue;
if(!vis[v])getscc(v);
}
}
void calc(int u,int p){
for(int i=0;i<l[u].size();i++){
int v = l[u][i].first;
int id = l[u][i].second;
if(v == p)continue;
d[v] = d[u] + 1;
par[v][0] = u;
be[v] = id;
for(int j=1;j<20;j++)
par[v][j] = par[par[v][j-1]][j-1];
calc(v,u);
}
}
int lca(int u,int v){
if(d[u] > d[v])swap(u,v);
int dif = d[v] - d[u];
assert(dif >=0);
for(int k=20;k>=0;k--){
if((dif >> k) & 1){
v = par[v][k];
}
}
if(v == u)return u;
for(int k=20;k>=0;k--){
if(par[u][k] != par[v][k]){
u = par[u][k];
v = par[v][k];
}
}
return par[u][0];
}
int main(){
memset(to,-1,sizeof(to));
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>u[i]>>v[i];
g[u[i]].push_back({v[i],i});
g[v[i]].push_back({u[i],i});
}
findbridges(1);
for(int i=1;i<=n;i++){
if(!vis[i]){
cmp++;
getscc(i);
}
}
for(int i=0;i<m;i++){
int x = u[i],y = v[i];
if(gid[x] == gid[y])ans[i] = 'B';
else{
l[gid[x]].push_back({gid[y],i});
l[gid[y]].push_back({gid[x],i});
}
}
d[1] = 1;
calc(gid[1],0);
int q;
cin>>q;
for(int i=0;i<q;i++){
int a,b;
cin>>a>>b;
a = gid[a];
b = gid[b];
int c = lca(a,b);
while(a != c){
// if(to[a] != -1){
// a = to[a];
// if(d[to[a]] > d[c])
// to[a] = c;
// continue;
// }
to[a] = c;
int p = par[a][0];
int x = u[be[a]],y = v[be[a]];
x = gid[x];
y = gid[y];
// cout << x << ' ' << y << endl;
if(x == a && y== p)ans[be[a]] = 'R';
else ans[be[a]] = 'L';
a = p;
}
while(b != c){
// if(to[b] != -1){
// b = to[b];
// if(d[to[b]] > d[c])
// to[b] = c;
// continue;
// }
to[b] = c;
int p = par[b][0];
int x = u[be[b]],y = v[be[b]];
x = gid[x];
y = gid[y];
if(x == b && y== p)ans[be[b]] = 'L';
else ans[be[b]] = 'R';
b = p;
}
}
for(int i=0;i<m;i++){
if(!ans[i])ans[i] = 'B';
cout << ans[i];
}
printf("\n");
}
Compilation message
oneway.cpp: In function 'void getscc(int)':
oneway.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[u].size();i++){
~^~~~~~~~~~~~
oneway.cpp: In function 'void calc(int, int)':
oneway.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<l[u].size();i++){
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
