#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, m, p;
vector<int> Adj[N], Adj2[N];
vector<ii> Adj3[N];
vector<ii> edges;
set<ii> bridges;
int cnt;
int ti[N], low[N];
char ans[N];
void dfs(int u, int p){
cnt++;
ti[u] = low[u] = cnt;
for(auto v : Adj[u]){
if(ti[v]){
if(v != p) low[u] = min(low[u], ti[v]);
}
else{
dfs(v, u);
low[u] = min(low[u], low[v]);
if(ti[u] < low[v]){
bridges.insert({min(u, v), max(u, v)});
}
}
}
}
int cnt_comp;
int comp[N];
void dfs2(int u){
//cout << u << "\n";
comp[u] = cnt_comp;
for(auto v : Adj2[u]){
if(comp[v]) continue;
dfs2(v);
}
}
int sz[N], rt[N], answ[N];
vector<ii> que[N];
set<ii> ques[N];// for component
int sparse[N][20], d[N];
int ind[N];
void dfs3(int u, int p){
for(auto it : Adj3[u]){
int v = it.fi;
if(v == p) continue;
d[v] = d[u] + 1;
sparse[v][0] = u;
for(int i = 1; i <= 19; i++) sparse[v][i] = sparse[sparse[v][i - 1]][i - 1];
//cout << v << "\n";
//for(int i = 0; i <= 19; i++) cout << sparse[v][i] << " ";
//cout << "\n";
ind[v] = it.se;
dfs3(v, u);
}
}
int lca(int x, int y){
if(d[x] > d[y]) swap(x, y);
//cout << x << " " << y << " " << d[x] << " " << d[y] << "\n";
for(int i = 19; i >= 0; i--){
if(d[y] >= (d[x] + (1LL << i))){
//cout << i << "\n";
y = sparse[y][i];
}
}
//cout << x << " " << y << "\n";
if(x == y) return x;
for(int i = 19; i >= 0; i--){
if(sparse[x][i] != sparse[y][i]){
x = sparse[x][i];
y = sparse[y][i];
}
}
return sparse[x][0];
}
int root(int x){
return (x == rt[x] ? x : rt[x] = root(rt[x]));
}
void merge(int x, int y){
x = root(x), y = root(y);
if(x == y) return;
if(sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y], rt[y] = x;
for(auto it : ques[y]) ques[x].insert(it);
ques[y].clear();
}
map<ii, vector<int>> mp;
void dfs4(int u, int p){
for(auto it : Adj3[u]){
int v = it.fi;
if(v == p) continue;
dfs4(v, u);
merge(u, v);
}
//return;
int temp = root(u);
for(auto it : que[u]) ques[temp].insert(it);
while(ques[temp].size() && (*ques[temp].begin()).fi >= d[u]) ques[temp].erase(ques[temp].begin());
if(ques[temp].size()){
bool x = (*ques[temp].begin()).se;
answ[ind[u]] = (!x ? u : p);
}
else ans[ind[u]] = 'B';
}
void process(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
int x, y;
cin >> x >> y;
edges.pb({x, y});
mp[{min(x, y), max(x, y)}].pb(i);
//Adj[x].pb(y);
//Adj[y].pb(x);
}
for(auto it : mp){
Adj[it.fi.fi].pb(it.fi.se);
Adj[it.fi.se].pb(it.fi.fi);
}
for(int i = 1; i <= n; i++) if(!ti[i]) dfs(i, i);
//for(auto it : bridges) cout << it.fi << " " << it.se << "\n";
for(int i = 0; i < m; i++){
if(mp[edges[i]].size() > 1){
ans[i] = 'B';
continue;
}
if(bridges.find({min(edges[i].fi, edges[i].se), max(edges[i].fi, edges[i].se)}) == bridges.end()){
ans[i] = 'B';
Adj2[edges[i].fi].pb(edges[i].se);
Adj2[edges[i].se].pb(edges[i].fi);
// cout << edges[i].fi << " " << edges[i].se << "\n";
continue;
}
//cout << i << "\n";
}
for(int i = 1; i <= n; i++){
if(!comp[i]){
cnt_comp++;
dfs2(i);
}
}
// return;
for(int i = 0; i < m; i++){
if(ans[i] != 'B'){
assert(comp[edges[i].fi] != comp[edges[i].se]);
//cout << edges[i].fi << " " << edges[i].se << "\n";
//cout << comp[edges[i].fi] << " " << comp[edges[i].se] << "\n";
Adj3[comp[edges[i].fi]].pb({comp[edges[i].se], i});
Adj3[comp[edges[i].se]].pb({comp[edges[i].fi], i});
}
}
//return;
for(int i = 1; i <= cnt_comp; i++) if(!d[i]) dfs3(i, i);
cin >> p;
for(int i = 1; i <= p; i++){
int x, y;
cin >> x >> y;
if(comp[x] == comp[y]) continue;
int z = lca(comp[x], comp[y]);
//cout << comp[x] << " " << comp[y] << " " << z << "\n";
que[comp[x]].pb({d[z], 0});
que[comp[y]].pb({d[z], 1});
}
for(int i = 1; i <= n; i++){
sz[i] = 1, rt[i] = i;
}
for(int i = 1; i <= cnt_comp; i++){
if(!d[i]){
// cout << i << "\n";
dfs4(i, i);
}
}
for(int i = 0; i < m; i++){
if(ans[i] != 'B'){
if(answ[i] == comp[edges[i].fi]) ans[i] = 'R';
else ans[i] = 'L';
}
//cout << i << " " << edges[i].fi << " " << edges[i].se << "\n";
cout << ans[i] << "";
}
}
signed main(){
ios_base::sync_with_stdio(0);
process();
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
42584 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
42580 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
42584 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
42580 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
42584 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
42580 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
