#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const ll inf = 1e18;
const ld eps = 1e-13;
const ll mod = 1e9+7;
const int i_inf = 1e9;
const int mxn = 1e5;
mt19937 _rand(time(NULL));
clock_t timer = clock();
int n, m;
vector<pii> g[mxn];
int ans[mxn];
int dep[mxn];
bool vis[mxn];
bool bridge[mxn];
void dfs0(int u, int ed){
vis[u] = true;
int mindepth = dep[u];
for(auto e : g[u]){
if(e.nd == ed) continue;
if(!vis[e.st]){
dep[e.st] = dep[u] + 1;
dfs0(e.st, e.nd);
}
mindepth = min(mindepth, dep[e.st]);
}
if(mindepth >= dep[u]){
bridge[ed] = true;
}
else{
dep[u] = mindepth;
}
}
int group[mxn];
int root[mxn];
void dfs1(int u, int col){
vis[u] = true;
group[u] = col;
for(auto e : g[u]){
if(vis[e.st] || bridge[e.nd]) continue;
dfs1(e.st, col);
}
}
vector<pii> tree[mxn];
int par[mxn];
int uped[mxn];
int sparse[mxn][20];
int depth[mxn];
void dfs2(int u){
vis[u] = true;
sparse[u][0] = par[u];
fr(i, 1, 20) sparse[u][i] = sparse[sparse[u][i-1]][i-1];
for(auto e : tree[u]){
if(vis[e.st]) continue;
par[e.st] = u;
depth[e.st] = depth[u] + 1;
uped[e.st] = e.nd;
dfs2(e.st);
}
}
int lca(int a, int b){
int d = min(depth[a], depth[b]);
for(int i = 19; i >= 0; i --){
if(depth[a] - (1<<i) >= d) a = sparse[a][i];
if(depth[b] - (1<<i) >= d) b = sparse[b][i];
}
if(a == b) return a;
for(int i = 19; i >= 0; i --){
if(sparse[a][i] != sparse[b][i]){
a = sparse[a][i];
b = sparse[b][i];
}
}
return sparse[a][0];
}
void solve(){
cin >> n >> m;
int l[m], r[m];
fr(i, 0, m){
int u, v;
cin >> u >> v;
--u, --v;
l[i] = u;
r[i] = v;
if(u == v){
continue;
}
g[u].pb({v, i});
g[v].pb({u, i});
}
fr(i, 0, n){
if(vis[i]) continue;
dfs0(i, -1);
}
memset(vis, false, sizeof(vis));
int col = 0;
fr(i, 0, n){
if(vis[i]) continue;
dfs1(i, col);
++col;
}
fr(i, 0, m){
if(!bridge[i] || l[i] == r[i]) continue;
int a = group[l[i]];
int b = group[r[i]];
tree[a].pb({b, i+1});
tree[b].pb({a, -(i+1)});
}
memset(vis, false, sizeof(vis));
fr(i, 0, col){
if(vis[i]) continue;
par[i] = i;
uped[i] = 0;
dfs2(i);
}
int p;
cin >> p;
bool answered[mxn];
memset(answered, false, sizeof(answered));
fr(i, 0, p){
int u, v;
cin >> u >> v;
--u, --v;
u = group[u];
v = group[v];
if(u == v) continue;
int k = lca(u, v);
while(!answered[u] || depth[u] >= depth[k]){
if(uped[u] == 0) break;
if(uped[u] < 0){
ans[(-uped[u])-1] = 1;
}
if(uped[u] > 0){
ans[uped[u]-1] = 2;
}
answered[u] = true;
u = par[u];
}
while(!answered[v] || depth[v] >= depth[k]){
if(uped[v] == 0) break;
if(uped[v] < 0){
ans[(-uped[v])-1] = 2;
}
if(uped[v] > 0){
ans[uped[v]-1] = 1;
}
answered[v] = true;
v = par[v];
}
}
fr(i, 0, m){
if(ans[i] == 0) cout<<'B';
else if(ans[i] == 1) cout<<'R';
else cout<<'L';
}
cout<<endl;
}
int main(){
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5248 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5376 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
5376 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5248 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5376 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
5376 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5248 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5376 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
5376 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
