//I love armpit fetish
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"
const int MAX_N = 100002;
const int LG_N = 19;
const int INF = 1e9;
struct edge {
int u, v;
};
int n, m, nTime, num[MAX_N], low[MAX_N], l[MAX_N], p[LG_N+2][MAX_N];
int nCC, cc_id[MAX_N], up_query[MAX_N], down_query[MAX_N];
bool bridge[MAX_N], visited[MAX_N];
edge e[MAX_N];
vector<pair<int, int> > g[MAX_N], tr[MAX_N];
char res[MAX_N];
void enter() {
cin >> n >> m;
for (int i=1; i<=m; ++i) {
cin >> e[i].u >> e[i].v;
g[e[i].u].push_back(make_pair(e[i].v, i));
g[e[i].v].push_back(make_pair(e[i].u, i));
}
}
void dfs(int u, int par) {
num[u] = low[u] = ++nTime;
bool ok = false;
for (int i=0; i<g[u].size(); ++i) {
int v = g[u][i].first, id = g[u][i].second;
if (v==par && !ok)
ok = true;
else {
if (num[v])
low[u] = min(low[u], num[v]);
else {
dfs(v, u);
low[u] = min(low[u], low[v]);
}
if (num[u]<low[v])
bridge[id] = true;
else
res[id] = 'B';
}
}
}
void find_connected_component(int u) {
cc_id[u] = nCC;
for (int i=0; i<g[u].size(); ++i) {
int v = g[u][i].first, id = g[u][i].second;
if (cc_id[v]==0 && !bridge[id])
find_connected_component(v);
}
}
void fix_root(int u) {
for (int i=0; i<tr[u].size(); ++i) {
int v = tr[u][i].first;
if (v!=p[0][u]) {
p[0][v] = u;
l[v] = l[u] + 1;
fix_root(v);
}
}
}
void init_tree() {
for (int i=1; i<=n; ++i)
if (num[i]==0)
dfs(1, 0);
for (int i=1; i<=n; ++i) {
if (cc_id[i]==0) {
++nCC;
find_connected_component(i);
}
}
//PR(bridge, m);
for (int i=1; i<=m; ++i) {
if (bridge[i]) {
int u = cc_id[e[i].u], v = cc_id[e[i].v];
tr[u].push_back(make_pair(v, i));
tr[v].push_back(make_pair(u, i));
}
}
n = nCC;
for (int i=1; i<=n; ++i) {
if (l[i]==0) {
l[i] = 1;
fix_root(i);
}
}
for (int i=1; i<=LG_N; ++i)
for (int j=1; j<=n; ++j)
p[i][j] = p[i-1][p[i-1][j]];
}
int lca(int x, int y) {
for (int k=LG_N; k>=0; --k)
if (l[p[k][x]]>=l[y])
x = p[k][x];
for (int k=LG_N; k>=0; --k)
if (l[p[k][y]]>=l[x])
y = p[k][y];
for (int k=LG_N; k>=0; --k) {
if (p[k][x]!=p[k][y]) {
x = p[k][x];
y = p[k][y];
}
}
while (x != y) {
x = p[0][x];
y = p[0][y];
}
return x;
}
void init_query() {
int nQuery;
cin >> nQuery;
while (nQuery--) {
int u, v;
cin >> u >> v;
u = cc_id[u], v = cc_id[v];
if (u!=v) {
//cerr << u << ' ' << v << '\n';
int anc = lca(u, v);
++up_query[u];
--up_query[anc];
++down_query[v];
--down_query[anc];
}
}
}
void solve(int u) {
visited[u] = true;
for (int i=0; i<tr[u].size(); ++i) {
int v = tr[u][i].first, id = tr[u][i].second;
if (v!=p[0][u]) {
solve(v);
up_query[u] += up_query[v];
down_query[u] += down_query[v];
if (up_query[v]>0)
res[id] = (make_pair(cc_id[e[id].u], cc_id[e[id].v])==make_pair(v, u) ? 'R' : 'L');
else if (down_query[v]>0)
res[id] = (make_pair(cc_id[e[id].u], cc_id[e[id].v])==make_pair(u, v) ? 'R' : 'L');
else
res[id] = 'B';
}
}
}
int main() {
//#define OFFLINE_JUDGE doraemon
#ifdef OFFLINE_JUDGE
freopen(FILE_NAME".inp", "r", stdin);
freopen(FILE_NAME".out", "w", stdout);
#endif
ios::sync_with_stdio(0); cin.tie(0);
enter();
init_tree();
init_query();
for (int i=1; i<=n; ++i)
if (!visited[i])
solve(i);
for (int i=1; i<=m; ++i)
cout << res[i];
}
Compilation message
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:39:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<g[u].size(); ++i) {
~^~~~~~~~~~~~
oneway.cpp: In function 'void find_connected_component(int)':
oneway.cpp:60:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<g[u].size(); ++i) {
~^~~~~~~~~~~~
oneway.cpp: In function 'void fix_root(int)':
oneway.cpp:68:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<tr[u].size(); ++i) {
~^~~~~~~~~~~~~
oneway.cpp: In function 'void solve(int)':
oneway.cpp:148:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<tr[u].size(); ++i) {
~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
