#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;
int n, m, p, time_;
vector<int> Vis, up, dpth, upx, upy, dis, fin, U, V;
vector<vector<int>> A, X, Y;
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);
}
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 (dis[X[u][i]] < dis[u] || fin[X[u][i]] > fin[u]) {
if (dis[X[u][i]] < dis[u] && fin[u] <fin[X[u][i]]) {
upx[u] = min(upx[u], dpth[X[u][i]]);
}
else {
upx[u] = -1;
}
}
}
for (int i = 0; i < Y[u].size(); i++) {
if (dis[Y[u][i]] < dis[u] || fin[Y[u][i]] > fin[u]) {
if (dis[Y[u][i]] < dis[u] && fin[u] <fin[Y[u][i]]) {
upy[u] = min(upy[u], dpth[Y[u][i]]);
}
else {
upy[u] = -1;
}
}
}
if (up[u] == dpth[u] && has[{u, p}] == 1) {
if (upy[u] < dpth[u] && upx[u] >= dpth[u]) {
if (dir[{u, p}]) {
go[{u, p}] = 1;
}
else {
go[{p, u}] = 1;
}
}
else if (upx[u] < dpth[u] && upy[u] >= dpth[u]) {
if (dir[{u, p}]) {
go[{p, u}] = 1;
}
else {
go[{u, p}] = 1;
}
}
}
}
void calc(int u) {
dis[u] = ++time_;
for (auto v : A[u]) {
if (!dis[v]) {
calc(v);
}
}
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);
}
calc(1);
dpth[1] = 0;
dfs(1);
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:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int i = 0; i < X[u].size(); i++) {
| ~~^~~~~~~~~~~~~
oneway.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int i = 0; i < Y[u].size(); i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
