#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define f first
#define s second
vector<vector<int>> ed;
map<pii, char> ans;
map<pii, bool> is_bridge;
map<pii, pii> bridge;
vector<int> ret;
vector<int> tin;
vector<int> cmp;
vector<bool> visited;
vector<int> sum;
int cur_t = 0;
int nxt = 1;
void findBridges(int cur, int pr){
visited[cur] = true;
tin[cur] = ++cur_t;
ret[cur] = tin[cur];
for (auto to : ed[cur]){
if (to == pr || to == cur) continue;
if (visited[to]) ret[cur] = min(ret[cur], tin[to]);
else {
findBridges(to, cur);
ret[cur] = min(ret[cur], ret[to]);
}
if (ret[to] > tin[cur]) is_bridge[{cur, to}] = is_bridge[{to, cur}] = true;
}
}
void dfs(int cur, int k){
visited[cur] = true;
cmp[cur] = k;
for (auto to : ed[cur]){
if (!is_bridge[{cur, to}]) {
if (!visited[to]) dfs(to, k);
ans[{cur, to}] = ans[{to, cur}] = 'B';
} else if (!visited[to]) dfs(to, nxt++);
}
}
void subtreeSum(int cur, int pr){
visited[cur] = true;
for (auto to : ed[cur]){
if (visited[cur]) continue;
subtreeSum(to, cur);
sum[cur] += sum[to];
}
}
void calcAns(int cur, int pr){
visited[cur] = true;
if (pr != -1){
int u = bridge[{cur, pr}].f;
int v = bridge[{cur, pr}].s;
if (sum[cur] > 0) {
ans[{u, v}] = 'R';
ans[{v, u}] = 'L';
}
else if (sum[cur] < 0) {
ans[{u, v}] = 'L';
ans[{v, u}] = 'R';
}
else ans[{u , v}] = ans[{v, u}] = 'B';
}
for (auto to : ed[cur]){
if (visited[to]) continue;
calcAns(to, cur);
}
}
void init(int n){
ed.resize(n+1);
tin.resize(n+1);
ret.resize(n+1);
cmp.resize(n+1);
sum.resize(n+1);
visited.resize(n+1);
}
int main() {
int n, m; cin >> n >> m;
init(n);
vector<pii> g(m);
for (int i = 0; i < m; ++i) {
int u, v; cin >> u >> v;
g[i].f = u; g[i].s = v;
ed[u].pb(v);
ed[v].pb(u);
}
for (int i = 1; i <= n; ++i){
if (!visited[i]) findBridges(i, -1);
}
visited.assign(n+1, false);
for (int i = 1; i <= n; ++i){
if (!visited[i]) dfs(i, nxt++);
}
vector<vector<int>> new_ed(n+1);
for (int i = 1; i <= n; ++i) {
for (auto to : ed[i]){
if (cmp[i] == cmp[to]) continue;
new_ed[cmp[i]].pb(cmp[to]);
bridge[{cmp[i], cmp[to]}] = {i, to};
bridge[{cmp[to], cmp[i]}] = {to, i};
}
}
ed = new_ed;
int p; cin >> p;
for (int i = 0; i < p; ++i) {
int u, v; cin >> u >> v;
sum[cmp[u]]++;
sum[cmp[v]]--;
}
visited.assign(n+1, false);
for (int i = 1; i <= n; ++i){
if (!visited[i]) subtreeSum(i, -1);
}
visited.assign(n+1, false);
for (int i = 1; i <= n; ++i){
if (!visited[i]) calcAns(i, -1);
}
for (int i = 0; i < m; ++i) {
if (g[i].f == g[i].s) ans[{g[i].f, g[i].s}] = 'B';
cout << ans[{g[i].f, g[i].s}];
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
