#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)
const int N = 1e5 + 5;
int n, m, q;
int U[N], V[N], col, color[N], direction[N];
bool is_bridge[N];
int tin[N], tout[N], tim, low[N], up[N][17], pa[N], sz[N];
int st[4*N];
int head[N], co, chain[N];
int p[N], ID;
vector <int> adj[N], tree[N], curr;
void dfs(int u, int f){
tin[u] = low[u] = ++tim;
up[u][0] = pa[u] = f;
sz[u] = 1;
f(i,1,17) up[u][i] = up[up[u][i-1]][i-1];
curr.push_back(u);
int r = 0;
for(int v: adj[u]){
if(v == f) {r++; continue; }
if(tin[v] == 0){
tree[u].push_back(v), tree[v].push_back(u);
dfs(v, u);
sz[u] += sz[v];
low[u] = min(low[u], low[v]);
}
else low[u] = min(low[u], tin[v]);
}
tout[u] = ++tim;
if(low[u] == tin[u] and r <= 1) {
col++;
while(!curr.empty()){
int w = curr.back();
color[w] = col;
curr.pop_back();
if(w == u) break;
}
if(f != 0)
is_bridge[u] = 1;
}
}
bool is(int u, int v){
return tin[u] <= tin[v] and tout[u] >= tout[v];
}
int lca(int u, int v){
if(is(u, v)) return u;
if(is(v, u)) return v;
fa(i,16,0){
if(up[u][i] == 0 or is(up[u][i], v)) continue;
u = up[u][i];
}
return up[u][0];
}
int node(int u, int v){
fa(i,16,0){
if(up[u][i] == 0 or is(up[u][i], v)) continue;
u = up[u][i];
}
return u;
}
void HLD(int u, int f){
chain[u] = co;
p[u] = ++ID;
tin[u] = ID;
int Bchild = -1, size = 0;
for(int v: tree[u]){
if(v == f) continue;
if(sz[v] > size){
size = sz[v];
Bchild = v;
}
}
if(Bchild != -1){
HLD(Bchild, u);
}
for(int v: tree[u]){
if(v != f and v != Bchild){
head[++co] = v;
HLD(v, u);
}
}
}
void Upd(int id, int l, int r, int x, int y, int val){
if(r < x or y < l) return;
if(x <= l and r <= y){
st[id] = val;
return;
}
int m = (l+r)>>1;
Upd(id<<1, l, m, x, y, val), Upd(id<<1|1, m+1, r, x, y, val);
}
int Query(int id, int l, int r, int x){
if(r < x or x < l) return 0;
if(st[id] != 0) return st[id];
if(l == r) return 0;
int m = (l+r)>>1;
if(x <= m) return Query(id<<1, l, m, x);
return Query(id<<1|1, m+1, r, x);
}
void upd(int from, int to, int val){
while(chain[from] != chain[to]){
int cur = chain[from];
Upd(1, 1, n, p[head[cur]], p[from], val);
from = up[head[cur]][0];
}
Upd(1, 1, n, p[to], p[from], val);
}
int main(){
cin >> n >> m;
f(i,0,m){
cin >> U[i] >> V[i];
if(U[i] != V[i])
adj[U[i]].push_back(V[i]), adj[V[i]].push_back(U[i]);
}
f(i,1,n+1) if(tin[i] == 0) dfs(i, 0);
f(i,1,n+1) tin[i] = 0;
f(i,1,n+1)
if(tin[i] == 0){
head[++co] = i;
HLD(i, 0);
}
cin >> q;
f(i,0,q){
int u, v;
cin >> u >> v;
if(color[u] == color[v]) continue;
int LCA = lca(u, v), x;
if(u != LCA){
x = node(u, LCA);
upd(u, x, 1);
}
if(v != LCA){
x = node(v, LCA);
upd(v, x, -1);
}
}
f(i,1,n+1){
if(is_bridge[i]) direction[i] = Query(1, 1, n, p[i]);
}
f(i,0,m){
if((pa[U[i]] == V[i] and direction[U[i]] == 1) or (pa[V[i]] == U[i] and direction[V[i]] == -1)) cout << 'R';
else if((pa[U[i]] == V[i] and direction[U[i]] == -1) or (pa[V[i]] == U[i] and direction[V[i]] == 1)) cout << 'L';
else cout << 'B';
}
cout << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
