//author: Ahmet Alp Orakci
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define ONLINE_JUDGE
void solve() {
int n, m;
cin >> n >> m;
map <pair <int, int>, int> mp;
vector <pair <int, int>> adj[n +1];
vector <pair <int, int>> edges(m);
for(int i = 0; i < m; i++) {
cin >> edges[i].first >> edges[i].second;
adj[edges[i].first].emplace_back(edges[i].second, i);
adj[edges[i].second].emplace_back(edges[i].first, i);
mp[{min(edges[i].first, edges[i].second), max(edges[i].first, edges[i].second)}]++;
}
int timer = 0;
vector <int> tin(n +1, -1), low(n +1, -1), is_bridge(m);
function <void(int, int)> dfs = [&](int node, int par) -> void {
low[node] = tin[node] = timer++;
for(auto [child, number] : adj[node]) {
if(child == par) {
continue;
}
if(tin[child] == -1) {
dfs(child, node);
low[node] = min(low[node], low[child]);
if(low[child] > tin[node]) {
//cerr << node << " " << child << " :: " << number << "\n";
is_bridge[number] = true;
}
} else {
low[node] = min(low[node], tin[child]);
}
}
};
for(int i = 1; i <= n; i++) {
if(tin[i] == -1) {
dfs(i, -1);
}
}
string res(m, 'B');
for(int i = 0; i < m; i++) {
if(mp[{min(edges[i].first, edges[i].second), max(edges[i].first, edges[i].second)}] > 1) {
//cerr << edges[i].first << " " << edges[i].second << " :: " << i << "\n";
is_bridge[i] = false;
}
if(is_bridge[i]) {
res[i] = 'X';
}
}
//cerr << res << "\n";
vector <int> compo(n +1, -1);
function <void(int, int)> dfsC = [&](int node, int color) {
compo[node] = color;
for(auto [child, num] : adj[node]) {
if(compo[child] == -1 && !is_bridge[num]) {
dfsC(child, color);
}
}
};
int col = 0;
for(int i = 1; i <= n; i++) {
if(compo[i] == -1) {
dfsC(i, col);
col++;
}
}
/*
for(int i = 1; i <= n; i++) {
cerr << compo[i] << " \n"[i == n];
}
*/
vector <pair <int, int>> nadj[col];
for(int i = 0; i < m; i++) {
if(is_bridge[i]) {
int x = compo[edges[i].first], y = compo[edges[i].second];
//cerr << i << " -> " << edges[i].first << " " << edges[i].second << " :: " << compo[edges[i].first] << " " << compo[edges[i].second] << "\n";
nadj[min(x, y)].emplace_back(max(x, y), i);
}
}
int p;
cin >> p;
vector <int> val(col);
for(int i = 1; i <= p; i++) {
int a, b;
cin >> a >> b;
//cerr << a << " " << b << " :: " << compo[a] << " " << compo[b] << "\n";
val[compo[a]]++;
val[compo[b]]--;
}
vector <int> vis(col, -1);
function <void(int)> DFS = [&](int node) -> void {
vis[node] = 0;
for(auto [child, num] : nadj[node]) {
if(vis[child] == -1)
DFS(child);
val[node] += val[child];
vis[node] = max(vis[node], vis[child] +1);
}
};
for(int i = 0; i < col; i++) {
if(vis[i] == -1) {
DFS(i);
}
}
for(int i = 0; i < m; i++) {
if(res[i] == 'X') {
int x = compo[edges[i].first], y = compo[edges[i].second];
//cerr << edges[i].first << " " << edges[i].second << " :: " << x << " " << y << " -> " << val[x] << " " << val[y] << "\n";
if(vis[x] > vis[y]) {
if(val[y] > 0)
res[i] = 'L';
else if(val[y] < 0)
res[i] = 'R';
else
res[i] = 'B';
} else if(x > y) {
if(val[x] > 0)
res[i] = 'R';
else if(val[x] < 0)
res[i] = 'L';
else
res[i] = 'B';
} else {
res[i] = 'B';
}
}
}
cout << res;
return;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t = 1; //cin >> t;
for(int i = 1; i <= t; i++) {
solve();
}
return 0;
}
| # |
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 |
- |
