#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }
template<typename T>
bool ckmn(T &x, T y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template<typename T>
bool ckmx(T &x, T y) {
if (x < y) {
x = y;
return true;
}
return false;
}
const int N = 100001, infI = 1e9 + 7;
const ll infL = 3e18;
int n, m, k;
int A[N], B[N], X[N], Y[N], tin[N], fup[N], T = 0, color[N], parent[N], idx_par[N], lca[N];
bool bridge[N], used[N];
vector<pair<int, int>> g[N], new_g[N], qu[N];
int p[N], sz[N], pp[N], ssz[N], leader[N], zz[N];
int get(int a) {
return a == p[a] ? a : p[a] = get(p[a]);
}
int gget(int a) {
return a == pp[a] ? a : pp[a] = gget(pp[a]);
}
int mrg(int a, int b) {
a = get(a);
b = get(b);
int newz = zz[a];
if (a == b) {
return 0;
}
if (sz[a] < sz[b]) {
swap(a, b);
}
sz[a] += sz[b];
p[b] = a;
zz[a] = newz;
return true;
}
int mmrg(int a, int b) {
a = gget(a);
b = gget(b);
assert(a != b);
if (ssz[a] < ssz[b]) {
swap(a, b);
}
ssz[a] += ssz[b];
pp[b] = a;
return a;
}
void dfs(int v, int j) {
tin[v] = fup[v] = T++;
used[v] = true;
for (auto [to, i]: g[v]) {
if (i != j) {
if (used[to]) {
ckmn(fup[v], tin[to]);
} else {
dfs(to, i);
ckmn(fup[v], fup[to]);
if (fup[to] > tin[v]) {
bridge[i] = true;
}
}
}
}
}
string ans;
void paint(int v) {
used[v] = true;
color[v] = T;
for (auto [to, i]: g[v]) {
if (!bridge[i] && !used[to]) {
paint(to);
}
}
}
void zhfs(int v) {
used[v] = true;
leader[v] = v;
for (auto [to, i]: new_g[v]) {
if (to != parent[v]) {
parent[to] = v;
idx_par[to] = i;
zhfs(to);
leader[mmrg(v, to)] = v;
}
}
for (auto[to, i] : qu[v]) {
if (used[to]) {
lca[i] = leader[gget(to)];
}
}
}
void union_path(int a, int c, int tp) {
a = get(a);
while (get(a) != get(c)) {
mrg(parent[a], a);
if (color[A[idx_par[a]]] == a) {
if (tp == 0) {
ans[idx_par[a]] = 'R';
} else {
ans[idx_par[a]] = 'L';
}
} else {
if (tp == 1) {
ans[idx_par[a]] = 'R';
} else {
ans[idx_par[a]] = 'L';
}
}
a = zz[get(a)];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> A[i] >> B[i];
--A[i], --B[i];
g[A[i]].emplace_back(B[i], i);
g[B[i]].emplace_back(A[i], i);
}
cin >> k;
for (int i = 0; i < k; ++i) {
cin >> X[i] >> Y[i];
--X[i], --Y[i];
}
iota(leader, leader + n, 0);
for (int i = 0; i < n; ++i) {
if (!used[i]) {
dfs(i, -1);
}
}
memset(used, 0, sizeof(used));
memset(idx_par, -1, sizeof(idx_par));
T = 0;
for (int i = 0; i < n; ++i) {
if (!used[i]) {
paint(i);
++T;
}
}
for (int i = 0; i < m; ++i) {
if (bridge[i]) {
new_g[color[A[i]]].emplace_back(color[B[i]], i);
new_g[color[B[i]]].emplace_back(color[A[i]], i);
}
}
for (int i = 0; i < k; ++i) {
qu[color[X[i]]].emplace_back(color[Y[i]], i);
qu[color[Y[i]]].emplace_back(color[X[i]], i);
}
memset(used, 0, sizeof(used));
fill(sz, sz + T, 1);
fill(ssz, ssz + T, 1);
iota(pp, pp + T, 0);
iota(p, p + T, 0);
for (int i = 0; i < T; ++i) {
if (!used[i]) {
zhfs(i);
}
}
ans = string(m, 'B');
for (int i = 0; i < k; ++i) {
int a = color[X[i]];
int b = color[Y[i]];
int c = lca[i];
union_path(a, c, 0);
union_path(b, c, 1);
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3043 ms |
7892 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3043 ms |
7892 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3043 ms |
7892 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
