#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define pb push_back
const int maxn5 = 1e6 + 10;
const int lg = 20;
int ty[maxn5], a[maxn5], b[maxn5], h[maxn5];
int par[lg + 2][maxn5], mn[maxn5], req[maxn5][2];
int cmp[maxn5], no = 0;
bool mark[maxn5], brsh[maxn5];
pair <int, int> e[maxn5];
vector <pair<int, int>> adj[maxn5], jda[maxn5];
inline void make_dir(int id, int u, int v){
//cout << "dir of " << id << ' ' << u << ' ' << v << endl;
ty[id] = 1;
if(u == cmp[e[id].fi] && v == cmp[e[id].se])
ty[id] = 2;
}
inline int lca(int a, int b){
if(h[a] < h[b])
swap(a, b);
int d = h[a] - h[b];
for(int i = 0; i < lg; i++) if((d >> i)&1)
a = par[i][a];
for(int i = lg - 1; i >= 0; i--) if(par[i][a] != par[i][b])
a = par[i][a], b = par[i][b];
return par[0][a];
}
inline void dfs_det(int v, int p){
mn[v] = h[v];
mark[v] = true;
for(auto [u, id] : adj[v]) if(id != p){
if(!mark[u]){
h[u] = h[v] + 1;
dfs_det(u, id);
mn[v] = min(mn[v], mn[u]);
if(mn[u] > h[v])
brsh[id] = true;
//cout << "det " << v << ' ' << u << ' ' << id << ' ' << mn[u] << ' ' << brsh[id] << endl;
}
else
mn[v] = min(mn[v], mn[u]);
}
return;
}
inline void dfs_bor(int v){
mark[v] = true;
cmp[v] = no;
//cout << "seeing " << v << ' ' << no << endl;
for(auto [u, id] : adj[v]) if(!mark[u] && !brsh[id]){
dfs_bor(u);
}
}
inline void dfs_lca(int v){
for(int i = 1; i < lg && par[i - 1][v] != -1; i++)
par[i][v] = par[i - 1][par[i - 1][v]];
for(auto [u, id] : jda[v]) if(u != par[0][v]){
par[0][u] = v;
h[u] = h[v] + 1;
dfs_lca(u);
}
}
inline void dfs_dir(int v){
for(auto [u, id] : jda[v]) if(u != par[0][v]){
dfs_dir(u);
if(req[u][0])
make_dir(id, u, v);
if(req[u][1])
make_dir(id, v, u);
req[v][0] += req[u][0];
req[v][1] += req[u][1];
}
return;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, m, p; cin >> n >> m;
for(int i = 0; i < m; i++){
int a, b; cin >> a >> b;
a--; b--;
adj[a].pb({b, i});
adj[b].pb({a, i});
e[i] = {a, b};
}
for(int i = 0; i < n; i++) if(!mark[i])
dfs_det(i, -1);
memset(mark, false, sizeof mark);
for(int i = 0; i < n; i++) if(!mark[i]){
dfs_bor(i);
no++;
}
for(int i = 0; i < n; i++) for(auto [u, id] : adj[i]) if(cmp[u] != cmp[i]){
jda[cmp[i]].pb({cmp[u], id});
//cout << "from " << i << ' ' << u << ' '<< id << ' '<< cmp[u] << ' ' << cmp[i] << endl;
}
memset(par, -1, sizeof par);
memset(h, 0, sizeof h);
for(int i = 0; i < n; i++) if(par[0][i] == -1)
dfs_lca(i);
cin >> p;
for(int i = 0; i < p; i++){
int a, b; cin >> a >> b;
a--; b--;
a = cmp[a];
b = cmp[b];
if(a == b)
continue;
int c = lca(a, b);
//cout << "for " << a << ' ' << b << ' ' << c << endl;
req[a][0]++;
req[b][1]++;
req[c][0]--;
req[c][1]--;
}
for(int i = 0; i < n; i++) if(par[0][i] == -1)
dfs_dir(i);
for(int i = 0; i < m; i++){
if(!brsh[i] || ty[i] == 0)
cout << 'B';
else
cout << (ty[i] == 1 ? 'L' : 'R');
}
cout << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
138316 KB |
Output is correct |
| 2 |
Correct |
64 ms |
138212 KB |
Output is correct |
| 3 |
Correct |
65 ms |
138392 KB |
Output is correct |
| 4 |
Correct |
65 ms |
138316 KB |
Output is correct |
| 5 |
Incorrect |
64 ms |
138440 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
138316 KB |
Output is correct |
| 2 |
Correct |
64 ms |
138212 KB |
Output is correct |
| 3 |
Correct |
65 ms |
138392 KB |
Output is correct |
| 4 |
Correct |
65 ms |
138316 KB |
Output is correct |
| 5 |
Incorrect |
64 ms |
138440 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
138316 KB |
Output is correct |
| 2 |
Correct |
64 ms |
138212 KB |
Output is correct |
| 3 |
Correct |
65 ms |
138392 KB |
Output is correct |
| 4 |
Correct |
65 ms |
138316 KB |
Output is correct |
| 5 |
Incorrect |
64 ms |
138440 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
