#include <iostream>
#include <vector>
#include <map>
using namespace std;
const int N = 1e5 + 10;
vector<vector<int>> nei[N];
map<int,int> seen[N];
int ans[N];
int Seen[N];
int mn[N];
bool cyc[N];
int h[N];
int T = 1;
int inf = 1e9;
int target;
int U[N],V[N];
bool Dfs(int u){
if (u==target)
return true;
if (Seen[u] == T)
return false;
Seen[u] = T;
for (vector<int> v : nei[u]){
int i = v[0];
int t = v[1];
int ind = v[2];
if (Dfs(i)){
ans[ind] |= t;
return true;
}
}
return false;
}
void dfs(int u,int p = -1,int hei = 1,int ind = 0){
// cout<<"arrived at "<<u<<" "<<hei<<endl;
mn[u] = inf;
h[u] = hei;
Seen[u] = T;
for (vector<int> v : nei[u]){
int i = v[0];
if (i==p)
continue;
if (Seen[i] == T){
cyc[v[2]] = true;
// cout<<"have already Seen"<<i<<" "<<h[i]<<endl;
mn[u] = min(mn[u],h[i]);
}
else{
dfs(i,u,hei+1,v[2]);
// cout<<"returned from "<<i<<" with mn "<<mn[i]<<endl;
mn[u] = min(mn[u],mn[i]);
}
}
if (mn[u]<hei)
cyc[ind] = true;
}
signed main(){
int n,m;
cin>>n>>m;
for (int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
U[i] = u;
V[i] = v;
seen[u][v]++;
seen[v][u]++;
if (seen[u][v]>1)
continue;
nei[u].push_back({v,1,i});
nei[v].push_back({u,2,i});
}
int p;
cin>>p;
while (p--){
int u;
cin>>u>>target;
T++;
Dfs(u);
}
T++;
for (int i=1;i<=n;i++)
h[i] = inf;
for (int i=1;i<=n;i++)
if (Seen[i]!=T)
dfs(i);
for (int i=1;i<=m;i++)
if (ans[i]==3 or cyc[i] or seen[U[i]][V[i]]>1)
cout<<"B";
else if (ans[i]==1)
cout<<"R";
else
cout<<"L";
cout<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
9560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
9560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
9560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
