/// In The Name Of God
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pp pop_back
#define mp make_pair
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define nl '\n'
#define ioi exit(0);
const int N = (int)1e5 + 7;
using namespace std;
int n, m, k;
pair <int, int> a[N], b[N];
char ans[N];
vector < pair <int, int> > g[N], g1[N];
int tmr, cnt;
vector <int> cur;
int dp[N], tin[N], id[N];
bool was[N], br[N];
void dfs(int v, int p = -1) {
was[v] = 1;
dp[v] = tin[v] = ++tmr;
for (auto to : g[v]) {
if (to.s == p) continue;
if (was[to.f]) dp[v] = min(dp[v], tin[to.f]);
else {
int fix = sz(cur);
dfs(to.f, to.s);
dp[v] = min(dp[v], dp[to.f]);
if (tin[v] < dp[to.f]) {
br[to.s] = 1;
++cnt;
while (sz(cur) != fix) {
id[cur.back()] = cnt;
cur.pp();
}
}
}
}
cur.pb(v);
}
void dfs1(int v, int p) {
was[v] = 1;
for (auto to : g1[v]) {
if (to.s == p) continue;
if (was[to.f]) assert(0);
dfs1(to.f, to.s);
dp[v] += dp[to.f];
if (!dp[to.f]) {
ans[to.s] = 'B';
} else if (dp[to.f] > 0) ans[to.s] = (id[a[to.s].f] == v) ? 'L' : 'R';
else ans[to.s] = (id[a[to.s].f] == v) ? 'R' : 'L';
}
}
int main() {
#ifdef IOI2018
freopen ("in.txt", "r", stdin);
#endif
Kazakhstan
cin >> n >> m;
rep(i, 1, m) {
cin >> a[i].f >> a[i].s;
g[a[i].f].pb({a[i].s, i});
g[a[i].s].pb({a[i].f, i});
}
cin >> k;
rep(i, 1, k) {
cin >> b[i].f >> b[i].s;
}
rep(i, 1, n) {
if (!was[i]) {
dfs(i);
++cnt;
while (sz(cur)) {
id[cur.back()] = cnt;
cur.pp();
}
}
}
rep(i, 1, m) {
if (!br[i]) {
ans[i] = 'B';
} else {
g1[a[i].f].pb({a[i].s, i});
g1[a[i].s].pb({a[i].f, i});
}
}
memset(dp, 0, sizeof(dp));
rep(i, 1, k) {
dp[b[i].f]++, dp[b[i].s]--;
}
memset(was, 0, sizeof(was));
rep(i, 1, cnt) {
if (!was[i]) dfs1(i, -1);
}
rep(i, 1, m) {
cout << ans[i];
}
ioi
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
