// Problem: https://oj.uz/problem/view/CEOI17_oneway
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define int long long
typedef pair<int, int> II;
typedef vector<II> VII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
#define PB push_back
#define F first
#define S second
#define ALL(a) a.begin(), a.end()
#define SET(a, b) memset(a, b, sizeof(a))
#define SZ(a) (int)(a.size())
#define FOR(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define fast_io \
ios_base::sync_with_stdio(false); \
cin.tie(NULL)
#define deb(a) cerr << #a << " = " << (a) << endl;
#define deb1(a) \
cerr << #a << " = [ "; \
for (auto it = a.begin(); it != a.end(); it++) cerr << *it << " "; \
cerr << "]\n";
#define endl "\n"
const long long mod = 1e9 + 7;
VVI g;
VI U, V, dep, up, bal;
string ans;
int other(int e, int u) { return U[e] ^ V[e] ^ u; }
void dfs(int u, int pe, int d) {
up[u] = dep[u] = d;
for (auto e : g[u]) {
int v = other(e, u);
if (e == pe) continue;
if (dep[v] == 0) {
dfs(v, e, d + 1);
if (up[v] <= d || bal[v] == 0)
ans[e] = 'B';
else {
ans[e] = 'R';
if (bal[v] < 0 && U[e] != u) // go towards v
ans[e] = 'L';
else if (bal[v] < 0 && U[e] == u) // come towards u
ans[e] = 'L';
}
bal[u] += bal[v];
} else {
up[u] = min(up[u], up[v]);
}
}
}
void solve() {
int n, m;
cin >> n >> m;
g = VVI(n, VI());
U = V = VI(m);
ans.assign(m, 'B');
dep = up = bal = VI(n, 0);
FOR(i, 0, m) {
cin >> U[i] >> V[i];
U[i]--, V[i]--;
g[U[i]].PB(i), g[V[i]].PB(i);
}
int p;
cin >> p;
while (p--) {
int a, b;
cin >> a >> b;
a--, b--;
bal[a]++;
bal[b]--;
}
FOR(i, 0, n) {
if (dep[i] == 0)
dfs(i, -1, 1);
}
cout << ans << endl;
}
signed main() {
fast_io;
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int totalTests = 1;
// cin >> totalTests;
for (int testNo = 1; testNo <= totalTests; testNo++) {
// cout << "Case #" << testNo << ": ";
solve();
}
return 0;
}
| # |
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 |
- |
