#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
using namespace std;
const int mxN = 3e5 + 227;
const int inf = 1e9 + 277;
const int mod = 24211007;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
struct DSU{
int n;
vector<int> lab;
DSU(){}
DSU(int _n) {
n = _n;
lab.resize(n + 7, -1);
}
int root(int u) {return lab[u] < 0 ? u : lab[u] = root(lab[u]);}
bool union_root(int u, int v)
{
u = root(u);
v = root(v);
if(u == v) return false;
if(lab[u] > lab[v]) swap(lab[u], lab[v]);
lab[u] += lab[v];
lab[v] = u;
return true;
}
} dsu;
int n;
int m;
vector<pair<int, int>> g[mxN];
vector<pair<int, int>> rg[mxN];
vector<pair<int, int>> adj[mxN];
vector<pair<int, int >> tree[mxN];
int p[mxN];
int depth[mxN];
int idx[mxN];
int low[mxN];
int num[mxN];
int ans[mxN];
int sub[mxN];
int id[mxN];
bool bridge[mxN];
bool vis[mxN];
bool mark[mxN];
int cur[mxN];
int timer = 0;
map<int, int> mp[mxN];
pair<int, int> edges[mxN];
multiset<int> ms1, ms2;
vector<int> node;
void dfs(int u, int par)
{
vis[u] = true;
low[u] = num[u] = ++timer;
for(auto it : adj[u]) {
int v = it.fi;
int idx = it.se;
if(v == par) continue;
if(num[v] == 0) {
dfs(v, u);
low[u] = min(low[u], low[v]);
if(low[v] == num[v] && mp[u][v] == 1) {
bridge[idx] = true;
}
}
else low[u] = min(low[u], num[v]);
}
}
void dfs_tree(int u, int par)
{
node.pb(u);
vis[u] = true;
id[u] = ++timer;
sub[u] = 1;
for(auto it: tree[u]) {
int v = it.fi;
if(v == par) continue;
dfs_tree(v, u);
sub[u] += sub[v];
}
}
void dfs_tree1(int u, int par)
{
for(auto it : tree[u]) {
int v = it.fi;
int idx = it.se;
if(v == par) continue;
dfs_tree1(v, u);
cur[u] += cur[v];
if(bridge[idx] == true && cur[v] > 0) {
if(edges[idx].fi == u) {
ans[idx] = 0;
}
else {
ans[idx] = 1;
}
}
}
for(auto it : g[u]) {
int v = it.fi;
int lef = id[u];
int rig = lef + sub[u] - 1;
if(lef <= id[v] && id[v] <= rig) {
}
else ++cur[u];
}
for(auto it : g[u]) {
int v = it.fi;
int lef = id[u];
int rig = lef + sub[u] - 1;
if(lef <= id[v] && id[v] <= rig) --cur[u];
}
}
void dfs_tree2(int u, int par)
{
for(auto it : tree[u]) {
int v = it.fi;
int idx = it.se;
if(v == par) continue;
dfs_tree2(v, u);
cur[u] += cur[v];
if(bridge[idx] == true && cur[v] > 0) {
if(edges[idx].fi == u) {
ans[idx] = 1;
}
else {
ans[idx] = 0;
}
}
}
for(auto it : rg[u]) {
int v = it.fi;
int lef = id[u];
int rig = lef + sub[u] - 1;
if(lef <= id[v] && id[v] <= rig) {
}
else ++cur[u];
}
for(auto it : g[u]) {
int v = it.fi;
int lef = id[u];
int rig = lef + sub[u] - 1;
if(lef <= id[v] && id[v] <= rig) --cur[u];
}
}
void solve()
{
cin >> n >> m;
dsu = DSU(n);
for(int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
if(dsu.union_root(u, v) == true) {
tree[u].pb({v, i});
tree[v].pb({u, i});
// cout << u << ' ' << v << endl;
}
adj[u].pb({v, i});
adj[v].pb({u, i});
mp[u][v]++;
mp[v][u]++;
edges[i] = {u, v};
}
int q;
cin >> q;
for(int i = 1; i <= q; i++) {
int u, v;
cin >> u >> v;
if(u == v) continue;
g[u].pb({v, i});
rg[v].pb({u, i});
}
for(int i = 1; i <= n; i++) {
if(!vis[i]) dfs(i, -1);
}
for(int i = 1; i <= m; i++) ans[i] = 2;
timer = 0;
for(int i = 1; i <= n; i++) vis[i] = false;
for(int j = 1; j <= n; j++) {
if(vis[j] == true) continue;
node.clear();
dfs_tree(j, -1);
dfs_tree1(j, -1);
for(int i : node) {
cur[i] = 0;
}
dfs_tree2(j, -1);
}
for(int i = 1; i <= m; i++) {
if(ans[i] == 0) cout << "L";
if(ans[i] == 1) cout << "R";
if(ans[i] == 2) cout << "B";
}
cout << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen(TASK".in" , "r" , stdin);
//freopen(TASK".out" , "w" , stdout);
int tc = 1;
// cin >> tc;
while(tc--) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
42572 KB |
Output is correct |
| 2 |
Correct |
22 ms |
42680 KB |
Output is correct |
| 3 |
Correct |
23 ms |
42788 KB |
Output is correct |
| 4 |
Incorrect |
23 ms |
42888 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
42572 KB |
Output is correct |
| 2 |
Correct |
22 ms |
42680 KB |
Output is correct |
| 3 |
Correct |
23 ms |
42788 KB |
Output is correct |
| 4 |
Incorrect |
23 ms |
42888 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
42572 KB |
Output is correct |
| 2 |
Correct |
22 ms |
42680 KB |
Output is correct |
| 3 |
Correct |
23 ms |
42788 KB |
Output is correct |
| 4 |
Incorrect |
23 ms |
42888 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
