#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){
//cout << "EDGE " << u << " " << ind[u] << "\n";
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 + 1;
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;
map<ii, vector<int>> mp2;
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());
// cout << u << " " << p << " " << ind[u] << " " << temp << " " << ques[temp].size() << "\n";
if(!ind[u]) return;
if(ques[temp].size()){
bool x = (*ques[temp].begin()).se;
answ[ind[u] - 1] = (!x ? u : p);
}
else{
ans[ind[u] - 1] = 'B';
// cout << ind[u] << "\n";
}
}
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);
}
}
// for(int i = 1; i <= n; i++) cout << i << " " << comp[i] << "\n";
// 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});
mp2[{min(comp[edges[i].fi], comp[edges[i].se]), max(comp[edges[i].fi], comp[edges[i].se])}].pb(i);
}
}
for(auto it : mp2){
if(it.se.size() > 1){
for(auto temp : it.se) ans[temp] = 'B';
}
int x = mp2[it.fi][0];
Adj3[it.fi.fi].pb({it.fi.se, x});
Adj3[it.fi.se].pb({it.fi.fi, x});
//cout << it.fi.fi << " " << it.fi.se << " " << x << "\n";
}
//return;
for(int i = 1; i <= cnt_comp; i++) if(!d[i]) dfs3(i, i);
//cout << "OK\n";
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();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
42652 KB |
Output is correct |
| 2 |
Correct |
22 ms |
42580 KB |
Output is correct |
| 3 |
Correct |
26 ms |
42956 KB |
Output is correct |
| 4 |
Correct |
23 ms |
43256 KB |
Output is correct |
| 5 |
Correct |
24 ms |
43360 KB |
Output is correct |
| 6 |
Correct |
21 ms |
42716 KB |
Output is correct |
| 7 |
Correct |
24 ms |
43256 KB |
Output is correct |
| 8 |
Correct |
23 ms |
43220 KB |
Output is correct |
| 9 |
Incorrect |
24 ms |
42868 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
42652 KB |
Output is correct |
| 2 |
Correct |
22 ms |
42580 KB |
Output is correct |
| 3 |
Correct |
26 ms |
42956 KB |
Output is correct |
| 4 |
Correct |
23 ms |
43256 KB |
Output is correct |
| 5 |
Correct |
24 ms |
43360 KB |
Output is correct |
| 6 |
Correct |
21 ms |
42716 KB |
Output is correct |
| 7 |
Correct |
24 ms |
43256 KB |
Output is correct |
| 8 |
Correct |
23 ms |
43220 KB |
Output is correct |
| 9 |
Incorrect |
24 ms |
42868 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
42652 KB |
Output is correct |
| 2 |
Correct |
22 ms |
42580 KB |
Output is correct |
| 3 |
Correct |
26 ms |
42956 KB |
Output is correct |
| 4 |
Correct |
23 ms |
43256 KB |
Output is correct |
| 5 |
Correct |
24 ms |
43360 KB |
Output is correct |
| 6 |
Correct |
21 ms |
42716 KB |
Output is correct |
| 7 |
Correct |
24 ms |
43256 KB |
Output is correct |
| 8 |
Correct |
23 ms |
43220 KB |
Output is correct |
| 9 |
Incorrect |
24 ms |
42868 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
