#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int inf = 1e9, lg = 20;
int n, m, p, time_;
vector<int> Vis, up, dpth, upx, upy, dis, fin, U, V;
vector<vector<int>> A, X, Y, Lca;
map<array<int, 2>, int> dir, has, go;
void pre() {
Vis.resize(n + 1), up.resize(n + 1, inf), dpth.resize(n + 1, inf), upx.resize(n + 1, inf), upy.resize(n + 1, inf), dis.resize(n + 1), fin.resize(n + 1), U.resize(m), V.resize(m);
A.resize(n + 1), X.resize(n + 1), Y.resize(n + 1), Lca.resize(n + 1, vector<int>(lg + 1));
}
int lca(int u, int v) {
if (dpth[u] > dpth[v]) {
swap(u, v);
}
for (int i = lg; i >= 0; i--) {
if (dpth[Lca[v][i]] >= dpth[u]) {
v = Lca[v][i];
}
}
for (int i = lg; i >= 0; i--) {
if (dpth[Lca[v][i]] != dpth[Lca[u][i]]) {
u = Lca[u][i], v = Lca[v][i];
}
}
if (u != v) {
u = Lca[u][0];
}
return u;
}
void dfs(int u, int p = -1) {
Vis[u] = 1;
up[u] = dpth[u];
for (auto v : A[u]) {
if (v == p) {
continue;
}
if (!Vis[v]) {
dpth[v] = dpth[u] + 1;
dfs(v, u);
upx[u] = min(upx[u], upx[v]);
upy[u] = min(upy[u], upy[v]);
}
up[u] = min(up[u], up[v]);
}
for (int i = 0; i < X[u].size(); i++) {
if (fin[X[u][i]] < dis[u] || dis[X[u][i]] > fin[u]) {
upx[u] = dpth[lca(u, X[u][i])];
}
upx[u] = min(upx[u], dpth[X[u][i]]);
}
for (int i = 0; i < Y[u].size(); i++) {
if (fin[Y[u][i]] < dis[u] || dis[Y[u][i]] > fin[u]) {
upy[u] = dpth[lca(u, Y[u][i])];
}
upy[u] = min(upy[u], dpth[Y[u][i]]);
}
if (up[u] == dpth[u] && has[{u, p}] == 1) {
if (upy[u] < dpth[u]) {
if (dir[{u, p}]) {
go[{u, p}] = 1;
}
else {
go[{p, u}] = 1;
}
}
else if (upx[u] < dpth[u]) {
if (dir[{u, p}]) {
go[{p, u}] = 1;
}
else {
go[{u, p}] = 1;
}
}
}
}
void calc(int u, int p = -1) {
dis[u] = ++time_;
Lca[u][0] = (p == -1 ? u : p);
for (int i = 1; i <= lg; i++) {
Lca[u][i] = Lca[Lca[u][i - 1]][i - 1];
}
for (auto v : A[u]) {
if (!dis[v]) {
dpth[v] = dpth[u] + 1;
calc(v, u);
}
}
fin[u] = ++time_;
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
cin >> n >> m;
pre();
for (int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
A[u].push_back(v);
A[v].push_back(u);
dir[{u, v}] = 1;
has[{u, v}]++;
has[{v, u}]++;
U[i] = u, V[i] = v;
}
cin >> p;
for (int i = 0 ; i < p; i++) {
int x, y;
cin >> x >> y;
X[y].push_back(x);
Y[x].push_back(y);
}
for (int i = 1; i <= n; i++) {
if (Vis[i]) {
continue;
}
dpth[i] = 0;
calc(i);
dfs(i);
}
for (int i = 0; i < m; i++) {
int u = U[i], v = V[i];
if (!(go[{u, v}] || go[{v, u}]) || u == v || has[{u, v}] != 1) {
cout << 'B';
continue;
}
if (go[{u, v}]) {
cout << 'R';
continue;
}
cout << 'L';
}
}
Compilation message
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i = 0; i < X[u].size(); i++) {
| ~~^~~~~~~~~~~~~
oneway.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (int i = 0; i < Y[u].size(); i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
