#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;
template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
for (auto &i : a) {
is >> i;
}
return is;
}
struct Edge {
int to, ind;
};
vector<vector<Edge>> g;
vector<bool> used;
vector<int> d, up;
vector<bool> br;
void dfs_bridges(int v, int depth = 0, int p = -1) {
used[v] = 1;
d[v] = up[v] = depth;
for (auto [u, ind] : g[v]) {
if (!used[u]) {
dfs_bridges(u, depth + 1, ind);
up[v] = min(up[v], up[u]);
if (d[v] < up[u]) {
br[ind] = true;
}
} else if (ind != p) {
up[v] = min(up[v], d[u]);
}
}
}
vector<int> c;
void dfs_color(int v, int cl) {
c[v] = cl;
for (auto [u, ind] : g[v]) {
if (c[u] == -1 && !br[ind]) {
dfs_color(u, cl);
}
}
}
vector<vector<Edge>> t;
vector<int> sum, ans;
void dfs_sum(int v, int p = -1) {
used[v] = 1;
for (auto [u, ind] : t[v]) {
if (u != p) {
dfs_sum(u, v);
sum[v] += sum[u];
if (sum[u] > 0) {
ans[ind] = 1;
} else if (sum[u] < 0) {
ans[ind] = -1;
}
}
}
}
int32_t main() {
#ifdef LOCAL
freopen("/tmp/input.txt", "r", stdin);
#else
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
int n, m;
cin >> n >> m;
g.resize(n);
vector<pair<int, int>> edg(m);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back({v, i});
g[v].push_back({u, i});
edg[i] = {u, v};
}
used.resize(n);
d.resize(n);
up.resize(n);
br.resize(m);
for (int i = 0; i < n; ++i) {
if (!used[i]) {
dfs_bridges(i);
}
}
c.resize(n, -1);
int cl = 0;
for (int i = 0; i < n; ++i) {
if (c[i] == -1) {
dfs_color(i, cl++);
}
}
t.resize(cl);
for (int i = 0; i < m; ++i) {
if (br[i]) {
auto [u, v] = edg[i];
t[c[u]].push_back({c[v], i});
t[c[v]].push_back({c[u], i});
}
}
int p;
cin >> p;
sum.resize(cl);
for (int i = 0; i < p; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
++sum[c[u]];
--sum[c[v]];
}
used.clear();
used.resize(cl);
ans.resize(m);
for (int i = 0; i < cl; ++i) {
if (!used[i]) {
dfs_sum(i);
}
}
for (int i = 0; i < m; ++i) {
auto [u, v] = edg[i];
if (c[u] == c[v]) {
cout << "B";
} else {
if (ans[i] == 1) {
cout << "R";
} else if (ans[i] == -1) {
cout << "L";
} else {
cout << "B";
}
}
}
cout << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
