#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 1e5+5;
int n, m, p;
map<pii, int> M;
vector<vector<int> > g(N), cc;
vector<pii> E;
int pre[N], low[N];
bitset<N> br;
void tarjan(int u, int p) {
static int idx = 0;
static stack<int> S;
pre[u] = low[u] = ++idx;
S.emplace(u);
for(int v : g[u]) if(v != p) {
if(!pre[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] > pre[u]) {
if(M.count(pii(u, v))) br[M[pii(u, v)]] = true;
else br[M[pii(v, u)]] = true;
cc.emplace_back(vector<int>());
while(cc.back().empty() || cc.back().back() != v) {
cc.back().emplace_back(S.top());
S.pop();
}
}
} else low[u] = min(low[u], pre[v]);
}
if(u == p) {
cc.emplace_back(vector<int>());
while(!S.empty()) {
cc.back().emplace_back(S.top());
S.pop();
}
}
}
int id[N];
void gen_bbt() {
g.clear(), M.clear();
g.emplace_back(vector<int>());
for(vector<int>& c : cc) {
g.emplace_back(vector<int>());
for(int v : c) id[v] = g.size() - 1;
}
for(int i = 1, a, b; i <= m; i++) if(br[i]) {
tie(a, b) = E[i-1];
M[pii(id[a], id[b])] = i;
M[pii(id[b], id[a])] = i;
g[id[a]].emplace_back(id[b]);
g[id[b]].emplace_back(id[a]);
}
}
int par[N][18], dep[N];
void dfs(int u, int p) {
dep[u] = dep[p] + 1, par[u][0] = p;
for(int i = 1; i <= 17; i++) par[u][i] = par[par[u][i-1]][i-1];
for(int v : g[u]) if(v != p) dfs(v, u);
}
int lca(int a, int b) {
if(dep[a] < dep[b]) swap(a, b);
for(int i = 17; ~i; i--) if(dep[par[a][i]] >= dep[b]) a = par[a][i];
if(a == b) return a;
for(int i = 17; ~i; i--) if(par[a][i] != par[b][i]) a = par[a][i], b = par[b][i];
return par[a][0];
}
int orient[N];
int main() {
scanf("%d %d", &n, &m);
for(int i = 1, a, b; i <= m; i++) {
scanf("%d %d", &a, &b);
M[pii(a, b)] = i;
E.emplace_back(a, b);
g[a].emplace_back(b), g[b].emplace_back(a);
}
for(int i = 1; i <= n; i++) if(!pre[i]) tarjan(i, i);
gen_bbt();
for(int i = 1; i < g.size(); i++) if(!dep[i]) dfs(i, i);
scanf("%d", &p);
for(int i = 1, a, b; i <= p; i++) {
scanf("%d %d", &a, &b);
a = id[a], b = id[b];
int l = lca(a, b);
while(a != l) {
int eid = M[pii(a, par[a][0])];
if(orient[eid] != 0) break;
if(id[E[eid-1].x] == a && id[E[eid-1].y] == par[a][0]) orient[eid] = 1;
else orient[eid] = -1;
a = par[a][0];
}
while(b != l) {
int eid = M[pii(b, par[b][0])];
if(orient[eid] != 0) break;
if(id[E[eid-1].x] == b && id[E[eid-1].y] == par[b][0]) orient[eid] = -1;
else orient[eid] = 1;
b = par[b][0];
}
}
for(int i = 1; i <= m; i++) {
if(orient[i] == 0) printf("B");
else if(orient[i] == 1) printf("R");
else printf("L");
}
printf("\n");
return 0;
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:97:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < g.size(); i++) if(!dep[i]) dfs(i, i);
~~^~~~~~~~~~
oneway.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &p);
~~~~~^~~~~~~~~~
oneway.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
3072 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
3072 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
3072 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
