#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
using namespace std;
const int N = 100005;
vector <pair<int,int> > v[N];
int tin[N],low[N],a[N],b[N],ID[N],idx,cnt,dp[N];
vector <int> adj[N],vec[N],comp[N],O[N],C[N];
set <int> open[N],close[N];
bool bridge[N],vis[N];
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){
comp[idx].pb(x);
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 fill(int x){
for (int V: comp[x]){
for (int y: O[V]){
if (close[x].find(y) == close[x].end())
open[x].insert(y);
else close[x].erase(close[x].find(y));
}
for (int y: C[V]){
if (open[x].find(y) == open[x].end())
close[x].insert(y);
else open[x].erase(open[x].find(y));
}
}
}
void dfs2(int x,int par){
vis[x] = 1;
dp[x] = dp[par] + 1;
fill(x);
for (int to: adj[x]){
if(to == par) continue;
dfs2(to,x);
for (int y: open[to]){
if (close[x].find(y) == close[x].end())
open[x].insert(y);
else close[x].erase(close[x].find(y));
}
for (int y: close[to]){
if (open[x].find(y) == open[x].end())
close[x].insert(y);
else open[x].erase(open[x].find(y));
}
}
// cout<<"x = "<<x<<endl;
// cout<<"open: ";
// for (auto y: open[x])
// cout<<y<<" ";
// cout<<endl;
// cout<<"close: ";
// for (auto y: close[x])
// cout<<y<<" ";
// cout<<endl;
}
int main (){
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int n,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++)
vis[i] = 0;
int k;
cin>>k;
for (int i = 1; i <= k; i++){
int x,y;
cin>>x>>y;
O[x].pb(i);
C[y].pb(i);
}
idx = 0;
for (int i = 1; i <= n; i++){
if (vis[i]) continue;
idx++;
dfs1(i);
for (int x: comp[idx])
ID[x] = idx;
}
for (int i = 1; i <= n; i++)
for (int x: vec[i]){
adj[i].pb(ID[x]);
adj[ID[x]].pb(i);
}
for (int i = 1; i <= n; i++)
vis[i] = 0;
dfs2(1,1);
for (int i = 1; i <= m; i++){
if (bridge[i] == 0) cout<<'B';
else{
int x = ID[a[i]],y = ID[b[i]],o,c;
if (dp[x] > dp[y]){
o = open[x].size(),c = close[x].size();
if(o && !c) cout<<'R';
else if (!o && c) cout<<'L';
else cout<<'B';
}else{
o = open[y].size(),c = close[y].size();
if(o && !c) cout<<'L';
else if (!o && c) cout<<'R';
else cout<<'B';
}
}
}
}
Compilation message
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:17:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
17 | for (auto [to,id]: v[x]){
| ^
oneway.cpp: In function 'void dfs1(int)':
oneway.cpp:34:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
34 | for (auto [to,id]: v[x]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
