#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "
#define ll long long
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < (int)v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) { cin >> p.first; return cin >> p.second; }
vector<vector<pair<int, int>>> adj;
vector<pair<int, int>> edges;
vector<bool> vis;
vector<int> dp, dep, start_below;
vector<int> start, en;
vector<pair<int, int>> back_edges; // alignment of the edges // 0 is don't flip
string ans;
void dfs(int u, int edgeID, int d = 0) {
// cout << pl(u) << endl;
if (vis[u]) return;
vis[u] = 1;
dep[u] = d;
start_below[u] = start[u] - en[u];
// cout << pl(u) << adj[u] << endl;
for (auto [v, id] : adj[u]) {
if (id == edgeID) continue;
if (!vis[v]) {
dfs(v, id, d + 1);
start_below[u] += start_below[v];
dp[u] += dp[v];
} else {
if (dep[u] > dep[v]) {
// goes up
dp[u]++;
} else {
dp[u]--;
}
}
}
// cout << pl(u) << pl(dp[u]) << endl;
if (u != 0 && dp[u] == 0) {
// back edge
if (start_below[u] != 0) {
bool dir = start_below[u] > 0;
// check what direction the edge was originally oriented
if (edges[edgeID].first == u) {
dir = !dir;
}
back_edges.emplace_back(edgeID, dir);
}
}
}
void solve() {
int n, m; cin >> n >> m;
adj.resize(n);
// dfsTree.resize(n);
vis.resize(n);
start_below.resize(n);
dp.resize(n);
start.resize(n);
en.resize(n);
dep.resize(n);
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
a--, b--;
if (a == b) continue;
edges.emplace_back(a, b);
adj[a].emplace_back(b, i);
adj[b].emplace_back(a, i);
}
int p; cin >> p;
for (int i = 0; i < p; i++) {
int a, b; cin >> a >> b;
a--, b--;
start[a]++;
en[b]++;
}
dfs(0, -1, 0);
// cout << pl(vis[1]) << endl;
ans = string(m, 'B');
for (auto [edge, dir] : back_edges) {
ans[edge] = (!dir ? 'R' : 'L');
}
cout << ans << endl;
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T--)
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
