/* I can do this all day */
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;
const int N = 1e5 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;
ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }
mt19937 rng(time(nullptr));
int n, m, H[N], mark[N], Up[N], king[N], Ans[N];
vector < pii > G[N], adj[N];
set < pii > st[N];
void dfs(int v, int last)
{
Up[v] = H[v];
mark[v] = 1;
for(auto [u, id] : G[v])
{
///printf("v = %d last = %d u = %d id = %d\n", v, last, u, id);
if((id ^ 1) == last) continue;
if(mark[u])
{
Up[v] = min(Up[v], H[u]);
}
else
{
H[u] = H[v] + 1;
dfs(u, id);
Up[v] = min(Up[v], Up[u]);
}
}
///printf("v = %d H = %d up = %d\n", v, H[v], Up[v]);
}
void dfs2(int v)
{
mark[v] = 1;
for(auto [u, id] : G[v])
{
if(mark[u]) continue;
if(Up[u] > H[v])
{
king[u] = u;
}
else
{
king[u] = king[v];
}
dfs2(u);
}
}
void solve(int v, int last)
{
for(auto [u, id] : adj[v])
{
if((id ^ 1) == last) continue;
solve(u, id);
if(SZ(st[u]) > SZ(st[v])) st[v].swap(st[u]);
for(auto now : st[u])
{
if(st[v].count({now.F ^ 1, now.S}))
{
st[v].erase({now.F ^ 1, now.S});
}
else
{
st[v].insert(now);
}
}
}
int side = (last & 1);
int fir = 0;
if(SZ(st[v]) != 0)
{
fir = (*st[v].begin()).F;
Ans[last >> 1] = (1 - fir) ^ side;
}
}
int main()
{
fast_io;
cin >> n >> m;
for(int i = 1; i <= m; i ++)
{
int a, b;
cin >> a >> b;
G[a].push_back({b, i << 1});
G[b].push_back({a, i << 1 | 1});
Ans[i] = -1;
}
dfs(1, 0);
memset(mark, 0, sizeof mark);
dfs2(king[1] = 1);
for(int i = 1; i <= n; i ++)
{
for(auto [u, id] : G[i])
{
if(king[u] != king[i])
{
adj[king[i]].push_back(Mp(king[u], id));
}
}
}
int q;
cin >> q;
for(int i = 0; i < q; i ++)
{
int a, b;
cin >> a >> b;
if(king[a] == king[b])
{
continue;
}
st[king[a]].insert({0, i});
st[king[b]].insert({1, i});
}
solve(1, 0);
for(int i = 1 ;i <= m; i ++)
{
if(Ans[i] == -1)
{
cout << "B";
}
else if(Ans[i] == 0)
{
cout << "R";
}
else
{
cout << "L";
}
}
return 0;
}
/* check corner case(n = 1?), watch for negetive index or overflow */
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
10052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
10052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
10052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
