#include <bits/stdc++.h>
using namespace std;
// clang-format off
template <typename T, typename = void> struct is_iterable : false_type {};template <typename T>struct is_iterable< T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>> : true_type {};template <typename T>typename enable_if<is_iterable<T>::value && !is_same<T, string>::value,ostream &>::type operator<<(ostream &cout, T const &v);template <typename A, typename B>ostream &operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")";}template <typename T>typename enable_if<is_iterable<T>::value && !is_same<T, string>::value, ostream &>::type operator<<(ostream &cout, T const &v) { cout << "["; for (auto it = v.begin(); it != v.end();) {cout << *it; if (++it != v.end()) cout << ", "; } return cout << "]";}
#ifdef LOCAL
void dbg_out() { cout << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif
// clang-format on
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
void solve() {
// open
int n, m, p;
cin >> n >> m;
vector e(n, vector<pii>());
vector<pii> edges(m);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a--, b--;
e[a].pb({b, i});
e[b].pb({a, i});
// debug(a, b);
edges[i] = {a, b};
}
cin >> p;
vector r(n, vector<int>());
vector<pii> rq(p);
for (int i = 0; i < p; i++) {
int x, y;
cin >> x >> y;
x--, y--;
// x going to y
r[x].pb(i);
r[y].pb(i);
rq[i] = {x, y};
}
vector<bool> v(n, false);
vector<int> depth(n, 0);
vector<int> parent(n, -1);
vector<int> parent_edge(n, -1);
vector<set<int>> reqs(n);
vector<int> tin(n, -1);
vector<int> tout(n, -1);
vector<int> ans(m, 0);
for (int i = 0; i < n; i++) {
if (v[i])
continue;
// returns num back edges
int cc = 0;
auto dfs = [&](auto &dfs, int g, int p, int d, int pi) -> int {
v[g] = true;
depth[g] = d;
parent[g] = p;
parent_edge[g] = pi;
tin[g] = cc++;
vector<pii> back_edges, rev_back_edges;
int num_add = 0, num_sub = 0;
int total_be = 0, total_up = 0, total_down = 0;
for (const auto &[u, idx] : e[g]) {
// debug(u, idx);
if (v[u]) {
if (idx != parent_edge[g] and depth[u] < depth[g]) {
// back edge
num_add++;
} else if (idx != parent_edge[u] and depth[u] > depth[g]) {
num_sub++;
}
} else {
int num_back_edges = dfs(dfs, u, g, d + 1, idx);
total_be += num_back_edges;
if (num_back_edges == 0) {
if (!reqs[u].empty()) {
int idx_beg = *reqs[u].begin();
const auto [f, l] = rq[idx_beg];
const auto [fu, lu] = edges[idx_beg];
if (tin[u] <= tin[f] and tout[u] >= tout[f]) {
// go out
ans[idx] = (u == fu ? 1 : 2);
} else {
ans[idx] = (u == fu ? 2 : 1);
}
}
}
if (reqs[u].size() > reqs[g].size()) {
swap(reqs[u], reqs[g]);
}
for (auto x : reqs[u]) {
if (reqs[g].count(x)) {
reqs[g].erase(x);
} else {
reqs[g].insert(x);
}
}
reqs[u].clear();
}
}
total_be += num_add - num_sub;
for (auto u : r[g]) {
if (reqs[g].count(u)) {
reqs[g].erase(u);
} else {
reqs[g].insert(u);
}
}
tout[g] = cc++;
return total_be;
};
dfs(dfs, i, -1, 0, -1);
}
for (int i = 0; i < m; i++) {
if (ans[i] == 0) {
cout << "B";
} else if (ans[i] == 1) {
cout << "L";
} else {
cout << "R";
}
}
cout << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(false);
ll T = 1;
// cin >> T;
for (int t = 0; t < T; t++)
solve();
cout.flush();
return 0;
}
Compilation message
oneway.cpp: In instantiation of 'solve()::<lambda(auto:23&, int, int, int, int)> [with auto:23 = solve()::<lambda(auto:23&, int, int, int, int)>]':
oneway.cpp:135:27: required from here
oneway.cpp:79:25: warning: unused variable 'total_up' [-Wunused-variable]
79 | int total_be = 0, total_up = 0, total_down = 0;
| ^~~~~~~~
oneway.cpp:79:39: warning: unused variable 'total_down' [-Wunused-variable]
79 | int total_be = 0, total_up = 0, total_down = 0;
| ^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
