#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
#define left (h<<1),l,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;
const int N = 100005;
int tin[N],low[N],a[N],b[N],ID[N],in[N],out[N],dp[N],d[25][N],n1[N],n2[N];
int t[5][4*N];
bool O[N],C[N],bridge[N],vis[N],op[N],cl[N];
vector <int> adj[N],vec[N];
vector <pair<int,int> > v[N];
int k,idx,cnt,n;
void upd(int h,int l,int r,int idx,int val){
if (l == r){
if (val == 0) t[1][h] = t[2][h] = val;
else{
t[1][h] = min(t[1][h],val);
t[2][h] = max(t[2][h],val);
}
return;
}
if (idx > ((l + r)>>1)) upd(right,idx,val);
else upd(left,idx,val);
t[1][h] = min(t[1][h*2],t[1][h*2+1]);
t[2][h] = max(t[2][h*2],t[2][h*2+1]);
}
pair <int,int> get(int h,int l,int r,int L,int R){
if (r < L || R < l) return {1e9+6,0};
if (L <= l && r <= R) return {t[1][h],t[2][h]};
pair <int,int> a = get(left,L,R),b = get(right,L,R);
return {min(a.f,b.f),max(a.s,b.s)};
}
void dfs(int x,int par){
vis[x] = 1;
tin[x] = low[x] = cnt++;
for (auto [to,id]: v[x]){
if (to == par) continue;
if (vis[to]){
low[x] = min(low[x], tin[to]);
}else{
dfs(to,x);
low[x] = min(low[x], low[to]);
if (low[to] > tin[x])
bridge[id] = 1;
}
}
}
void dfs1(int x){
ID[x] = idx;
vis[x] = 1;
for (auto [to,id]: v[x]){
if (!vis[to] && !bridge[id]) dfs1(to);
else if (!vis[to] && bridge[id]) vec[idx].pb(to);
}
}
void dfs2(int x,int par){
vis[x] = 1;
in[x] = ++cnt;
d[0][x] = par;
dp[x] = dp[par] + 1;
for (int to: adj[x])
if (!vis[to]) dfs2(to,x);
out[x] = cnt;
}
void dfs3(int x,int par){
vis[x] = 1;
for (int to: adj[x])
if (to != par) dfs3(to,x);
// cout<<"x = "<<x<<endl;
// cout<<"o: ";
if (op[x]) upd(1,1,n,in[x],-1); /*cout<<x;*/
// cout<<endl;
// cout<<"c: ";
if (cl[x]) upd(1,1,n,in[x],1e9); /*cout<<x;*/
// cout<<endl;
// cout<<"VVV: ";
for (int id: vec[x]) upd(1,1,n,in[n1[id]],0),upd(1,1,n,in[n2[id]],0);
// cout<<id<<" ";
// cout<<endl;
pair <int,int> res = get(1,1,n,in[x],out[x]);
O[x] = (res.f == -1);
C[x] = (res.s == 1e9);
}
int lca(int x,int y){
if (dp[x] < dp[y]) swap(x,y);
for (int j = 18; j >= 0; j--)
if (dp[d[j][x]] >= dp[y]) x = d[j][x];
if (x == y) return x;
for (int j = 18; j >=0; j--)
if(d[j][x] != d[j][y]) x = d[j][x],y = d[j][y];
return d[0][x];
}
int main (){
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int m;
cin>>n>>m;
for (int i = 1; i <= m; i++){
cin>>a[i]>>b[i];
v[a[i]].pb({b[i],i});
v[b[i]].pb({a[i],i});
}
for (int i= 1; i <= n; i++)
if (!vis[i]) dfs(i,i);
for (int i = 1; i <= n; i++) {
sort(v[i].begin(),v[i].end());
for (int j = 1; j < v[i].size(); j++)
if (v[i][j].f == v[i][j - 1].f) bridge[v[i][j].s] = bridge[v[i][j - 1].s] = 0;
}
for (int i= 1; i <= n; i++) vis[i] = 0;
idx = 0;
for (int i = 1; i <= n; i++)
if (!vis[i]) idx++,dfs1(i);
for (int i = 1; i <= n; i++)
for (int x: vec[i])
adj[i].pb(ID[x]),adj[ID[x]].pb(i);
for (int j = 1; j < 19; j++)
for (int i = 1; i <= n; i++)
d[j][i] = d[j - 1][d[j - 1][i]];
for (int i = 1; i <= n; i++)
vec[i].clear(),vis[i] = 0;
cnt=0;
for (int i = 1; i <= n; i++)
if (!vis[i]) dfs2(i,i);
cin>>k;
for (int i = 1; i <= k; i++){
cin>>n1[i]>>n2[i];
n1[i] = ID[n1[i]],n2[i] = ID[n2[i]];
int c = lca(n1[i],n2[i]);
vec[c].pb(i);
// cout<<n1[i] << " & "<<n2[i]<<" "<<c<<endl;
op[n1[i]] = 1;
cl[n2[i]] = 1;
}
for (int i = 1; i <= n; i++) vis[i] = 0;
for (int i = 1; i <= n; i++)
if (!vis[i]) dfs3(i,i);
for (int i = 1; i <= m; i++){
if (!bridge[i]) cout<<'B';
else{
// cout<<a[i] << " ^ "<<b[i]<<endl;
int x = ID[a[i]],y = ID[b[i]];
// cout<<x<<" "<<y<<" | "<<O[x]<<" "<<C[x]<<endl;;
if (dp[x] >= dp[y]){
if(O[x] && !C[x]) cout<<'R';
else if (!O[x] && C[x]) cout<<'L';
else cout<<'B';
}else{
if(O[y] && !C[y]) cout<<'L';
else if (!O[y] && C[y]) cout<<'R';
else cout<<'B';
}
}
}
}
Compilation message
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:42:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
42 | for (auto [to,id]: v[x]){
| ^
oneway.cpp: In function 'void dfs1(int)':
oneway.cpp:57:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
57 | for (auto [to,id]: v[x]){
| ^
oneway.cpp: In function 'int main()':
oneway.cpp:118:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for (int j = 1; j < v[i].size(); j++)
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7504 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
7764 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7504 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
7764 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7504 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
7764 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
