#include <bits/stdc++.h>
using namespace std;
#define ar array< int , 2>
#define MASK(i) (1 << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
const int MAX = 1e6 + 1000, LOG = 20;
int n, x[MAX], y[MAX], high[MAX], f[LOG + 1][MAX], q, c[MAX], cnt, Count, num[MAX], low[MAX], m, a, b, z;
vector < int > A[MAX], B[MAX], C;
stack< int > st;
bool d[MAX], t[MAX];
map< int, string > dd[MAX];
struct DSU
{
vector < int > ff;
void Init(int n) { ff.resize(n + 100, -1);}
int Root(int x) {return (ff[x] <= -1 ? x : ff[x] = Root(ff[x]));}
bool Join(int x, int y)
{
int xx = Root(x);
int yy = Root(y);
if (xx == yy) return false;
//if (f[xx] > f[yy]) swap(xx, yy);
ff[xx] += ff[yy];
ff[yy] = xx;
return true;
}
bool Check(int x, int y) {return Root(x) == Root(y);}
};
DSU dsu1;
DSU dsu2;
void DFS(int x, int p)
{
for (int k = 1; k <= LOG; k++)
{
f[k][x] = f[k - 1][f[k - 1][x]];
}
for (int y : B[x])
{
if (p != y)
{
f[0][y] = x;
high[y] = high[x] + 1;
DFS(y, x);
}
}
}
void Prepare(int x)
{
high[0] = -1;
high[x] = 0;
DFS(x, 0);
}
int LCA(int x, int y)
{
if (high[x] < high[y]) return LCA(y, x);
for (int k = LOG; k >= 0; k--)
{
if (high[f[k][x]] >= high[y])
x = f[k][x];
}
for (int k = LOG; k >= 0; k--)
{
if (f[k][x] != f[k][y])
{
x = f[k][x];
y = f[k][y];
}
}
while (x != y)
{
x = f[0][x];
y = f[0][y];
}
return x;
}
void Visit(int x, int p)
{
num[x] = low[x] = ++Count;
//st.push(x);
int numChild = 0;
for (int y : A[x])
{
if (y != p)
{
if (num[y])
{
low[x] = min(low[x], num[y]);
}
else
{
Visit(y, x);
numChild++;
low[x] = min(low[x], low[y]);
if (low[y] >= num[y])
{
B[y].push_back(x);
B[x].push_back(y);
dsu1.Join(x, y);
t[x] = true;
t[y] = true;
}
if (x == p) {
if (numChild >= 2)
c[x] = true;
} else {
if (low[y] >= num[x])
c[x] = true;
}
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
memset(high, 0x3f, sizeof high);
dsu1.Init(n);
dsu2.Init(n);
for (int i = 1; i <= m; i++)
{
cin >> x[i] >> y[i];
A[x[i]].push_back(y[i]);
A[y[i]].push_back(x[i]);
}
for (int i = 1; i <= n; i++)
{
if (!num[i]) Visit(i, i);
}
int root = -1;
for (int i = 1; i <= n; i++)
{
if (c[i] == 1 && !d[dsu1.Root(i)])
{
d[dsu1.Root(i)] = 1;
C.push_back(i);
root = i;
}
}
for (int i = 0; i < C.size(); i++)
for (int j = i + 1; j < C.size(); j++)
{
if (dsu1.Join(C[i], C[j]))
{
B[C[i]].push_back(C[j]);
B[C[j]].push_back(C[i]);
dd[C[i]][C[j]] = "B";
dd[C[i]][C[j]] = "B";
}
}
Prepare(root);
cin >> q;
for (int i = 1; i <= q; i++)
{
cin >> a >> b;
if (t[a] == 0 || t[b] == 0) continue;
z = LCA(a, b);
z = dsu2.Root(z);
while (true)
{
a = dsu2.Root(a);
//cout << a << " " << z << endl;
if (a == z) break;
for (int i : B[a])
{
if (high[i] < high[a])
{
dsu2.Join(i, a);
if (dd[a][i] == "") {
dd[a][i] = "R";
dd[i][a] = "L";
}
a = i;
break;
}
}
}
while (true)
{
b = dsu2.Root(b);
//cout << b << " " << z << endl;
if (b == z) break;
for (int i : B[b])
{
if (high[i] < high[b])
{
dsu2.Join(i, b);
if (dd[b][i] == "") {
dd[b][i] = "L";
dd[i][b] = "R";
}
b = i;
break;
}
}
}
}
for (int i = 1; i <= m; i++)
{
if (t[x[i]] == 0 || t[y[i]] == 0 || dd[x[i]][y[i]] == "") cout << "B";
else cout << dd[x[i]][y[i]];
}
}
/*
8 11
1 2
1 2
4 3
2 3
1 3
5 1
5 2
5 6
4 5
7 3
8 7
1
6 8
*/
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:145:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for (int i = 0; i < C.size(); i++)
| ~~^~~~~~~~~~
oneway.cpp:146:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for (int j = i + 1; j < C.size(); j++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
98380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
98380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
98380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
