This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, cnt, q;
vector <int> e[N], stk;
vector <pair <int, int> > g[N];
int num[N], low[N], ti, comp[N], w[N];
void dfs(int u, int p) {
stk.push_back(u);
low[u] = num[u] = ++ti;
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i].first;
int id = g[u][i].second;
if (id == p) continue;
if (comp[v]) continue;
if (!num[v]) {
dfs(v, id);
low[u] = min(low[u], low[v]);
} else low[u] = min(low[u], num[v]);
}
if (low[u] == num[u]) {
++m;
while (stk.size()) {
int v = stk.back();
stk.pop_back();
comp[v] = m;
for (auto w: g[v]) {
if (comp[w.first] && m != comp[w.first]) e[m].push_back(comp[w.first]);
}
if (v == u) break;
}
}
}
void pull(int u) {
num[u] = 1;
for (auto v: e[u]) {
if (!num[v]) pull(v);
w[u] += w[v];
}
}
int main() {
ios :: sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
vector <pair <int, int> > edges;
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back({v, i});
g[v].push_back({u, i});
edges.push_back({u, v});
}
m = 0;
for (int i = 1; i <= n; ++i) {
if (num[i]) continue;
dfs(i, 0);
}
cin >> q;
while (q--) {
int u, v;
cin >> u >> v;
u = comp[u], v = comp[v];
if (u == v) continue;
++w[u], --w[v];
}
memset(num, 0, sizeof(num));
for (int i = 1; i <= m; ++i) {
if (num[i]) continue;
pull(i);
}
for (int i = 0; i < edges.size(); ++i) {
int u = edges[i].first;
int v = edges[i].second;
u = comp[u], v = comp[v];
if (u == v) {
cout << 'B';
continue;
}
if (u > v) {
if (w[v] < 0) cout << 'R';
if (w[v] > 0) cout << 'L';
if (w[v] == 0) cout << 'B';
} else {
if (w[u] < 0) cout << 'L';
if (w[u] > 0) cout << 'R';
if (w[u] == 0) cout << 'B';
}
}
}
Compilation message (stderr)
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for (int i = 0; i < g[u].size(); ++i) {
| ~~^~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for (int i = 0; i < edges.size(); ++i) {
| ~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |