#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename T, typename cmp = less<T>>
using ordered_set = tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;
constexpr int N = 1e5 + 5;
vi adj[N], g[N];
int l[N], r[N];
int ans[N];
int x[N], y[N];
bool is_bridge[N];
int disc[N], low[N];
void dfs(int u, int p = -1) {
static int t = 0;
disc[u] = low[u] = ++t;
for(int id: adj[u]) {
int v = l[id] + r[id] - u;
if(v == p) continue;
if(disc[v]) low[u] = min(low[u], disc[v]);
else {
dfs(v, u);
low[u] = min(low[u], low[v]);
if(low[v] > disc[u]) is_bridge[id] = 1;
}
}
}
int d[N];
int grp[N];
int find(int x) {return d[x] < 0 ? x : d[x] = find(d[x]);}
void join(int x, int y) {
x = find(x), y = find(y);
if(x == y) return;
if(d[x] > d[y]) swap(x, y);
d[x] += d[y]; d[y] = x;
}
constexpr int L = 17;
int pedge[N];
int par[N][L], lz[N][L];
int dep[N];
void dfs2(int u, int p) {
rep1(i, L - 1) par[u][i] = par[par[u][i - 1]][i - 1];
for(int id: g[u]) {
int v = l[id] + r[id] - u;
if(v != p) {
pedge[v] = id;
dep[v] = dep[u] + 1;
par[v][0] = u;
dfs2(v, u);
}
}
}
int lca(int u, int v) {
if(dep[u] > dep[v]) swap(u, v);
for(int i = L - 1; ~i; i--) if(dep[v] - (1 << i) >= dep[u]) {
v = par[v][i];
}
if(u == v) return u;
for(int i = L - 1; ~i; i--) if(par[u][i] != par[v][i]) {
u = par[u][i];
v = par[v][i];
}
return par[u][0];
}
void upd(int u, int v, int x) {
for(int i = L - 1; ~i; i--) if(dep[u] - (1 << i) >= dep[v]) {
lz[u][i] = x;
u = par[u][i];
}
}
int32_t main() {
fastio;
int n, m; cin >> n >> m;
rep(i, m) {
cin >> l[i] >> r[i]; --l[i], --r[i];
adj[r[i]].pb(i);
adj[l[i]].pb(i);
}
rep(i, n) if(!disc[i]) dfs(i);
memset(d, -1, sizeof(d));
memset(ans, -1, sizeof(ans));
rep(i, m) if(!is_bridge[i]) join(l[i], r[i]);
memset(grp, -1, sizeof(grp));
int k = 0;
rep(i, n) {
int r = find(i);
if(!~grp[r]) grp[r] = k++;
grp[i] = grp[r];
}
rep(i, m) if(is_bridge[i]) {
l[i] = grp[l[i]];
r[i] = grp[r[i]];
g[l[i]].pb(i);
g[r[i]].pb(i);
}
memset(pedge, -1, sizeof(pedge));
memset(par, -1, sizeof(par));
memset(lz, -1, sizeof(lz));
rep(i, k) if(!~par[i][0]) dfs2(i, i);
int p; cin >> p;
while(p--) {
int x, y; cin >> x >> y; --x, --y;
x = grp[x], y = grp[y];
if(x == y) continue;
int v = lca(x, y);
upd(x, v, 1);
upd(y, v, 0);
}
for(int i = L - 1; i; i--) {
rep(u, k) if(~lz[u][i]) {
lz[u][i - 1] = lz[u][i];
lz[par[u][i - 1]][i - 1] = lz[u][i];
}
}
rep(i, k) {
int id = pedge[i];
if(~lz[i][0]) {
assert(id != -1);
ans[id] = lz[i][0] ^ (i == l[id]);
}
}
rep(i, m) cout << (!~ans[i] ? 'B' : ans[i] ? 'L' : 'R');
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
19920 KB |
Output is correct |
| 2 |
Correct |
9 ms |
19796 KB |
Output is correct |
| 3 |
Correct |
9 ms |
19872 KB |
Output is correct |
| 4 |
Correct |
9 ms |
19924 KB |
Output is correct |
| 5 |
Correct |
10 ms |
19924 KB |
Output is correct |
| 6 |
Correct |
9 ms |
19924 KB |
Output is correct |
| 7 |
Correct |
9 ms |
19924 KB |
Output is correct |
| 8 |
Correct |
10 ms |
20052 KB |
Output is correct |
| 9 |
Runtime error |
216 ms |
262144 KB |
Execution killed with signal 9 |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
19920 KB |
Output is correct |
| 2 |
Correct |
9 ms |
19796 KB |
Output is correct |
| 3 |
Correct |
9 ms |
19872 KB |
Output is correct |
| 4 |
Correct |
9 ms |
19924 KB |
Output is correct |
| 5 |
Correct |
10 ms |
19924 KB |
Output is correct |
| 6 |
Correct |
9 ms |
19924 KB |
Output is correct |
| 7 |
Correct |
9 ms |
19924 KB |
Output is correct |
| 8 |
Correct |
10 ms |
20052 KB |
Output is correct |
| 9 |
Runtime error |
216 ms |
262144 KB |
Execution killed with signal 9 |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
19920 KB |
Output is correct |
| 2 |
Correct |
9 ms |
19796 KB |
Output is correct |
| 3 |
Correct |
9 ms |
19872 KB |
Output is correct |
| 4 |
Correct |
9 ms |
19924 KB |
Output is correct |
| 5 |
Correct |
10 ms |
19924 KB |
Output is correct |
| 6 |
Correct |
9 ms |
19924 KB |
Output is correct |
| 7 |
Correct |
9 ms |
19924 KB |
Output is correct |
| 8 |
Correct |
10 ms |
20052 KB |
Output is correct |
| 9 |
Runtime error |
216 ms |
262144 KB |
Execution killed with signal 9 |
| 10 |
Halted |
0 ms |
0 KB |
- |
