#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define ull unsigned long long
#define pll pair<ll, ll>
#define mp make_pair
#define ll long long
#define pb push_back
#define deb(x) cout << #x << " = " << x << endl
#define all(x) x.begin(), x.end()
#define ld long double
const ll mod = (ll)1e9 + 7;
const ll BASE = 47;
const ll inf = (ll)1e18;
const long double pi = 3.141592653;
const ld EPS = 1e-9;
using namespace std;
template <class T>
istream& operator>>(istream &in, vector<T> &arr) {
for (T &cnt : arr) {
in >> cnt;
}
return in;
};
struct edge {
ll u, ind;
};
vector<vector<edge>> g;
vector<pair<ll, ll>> directions;
vector<ll> tin, up;
vector<bool> bridge;
vector<bool> used;
vector<ll> comp;
ll L = 20;
vector<vector<ll>> dp;
vector<ll> tout, pred, pr_edge, limit;
ll timer = 0;
void dfs1(ll v, ll pr) {
tin[v] = timer;
up[v] = timer;
timer++;
used[v] = true;
for (auto e : g[v]) {
if (e.ind == pr) {
continue;
}
if (used[e.u]) {
up[v] = min(up[v], tin[e.u]);
continue;
}
dfs1(e.u, e.ind);
if (up[e.u] > tin[v]) {
bridge[e.ind] = true;
}
}
}
void dfs2(ll v) {
used[v] = true;
comp[v] = timer;
for (auto e : g[v]) {
if (used[e.u] or bridge[e.ind]) {
continue;
}
dfs2(e.u);
}
}
void dfs3(ll v, ll pr) {
tin[v] = timer;
used[v] = true;
timer++;
dp[v][0] = pr;
for (int i = 1; i < L; i++) {
dp[v][i] = dp[dp[v][i - 1]][i - 1];
}
for (auto e : g[v]) {
if (!used[e.u]) {
pred[e.u] = v;
pr_edge[e.u] = e.ind;
dfs3(e.u, v);
}
}
tout[v] = timer;
timer++;
}
bool parent(ll v, ll u) {
return (tin[v] <= tin[u] and tout[v] >= tout[u]);
}
ll lca (ll v, ll u) {
if (parent(v, u)) {
return v;
}
if (parent(u, v)) {
return u;
}
ll cnt = v;
for (int i = L - 1; i >= 0; i--) {
if (!parent(dp[cnt][i], u)) {
cnt = dp[cnt][i];
}
}
return dp[cnt][0];
}
void solve() {
ll n, m;
cin >> n >> m;
g.resize(n);
directions.resize(m);
used.resize(n, false);
for (int i = 0; i < m; i++) {
ll a, b;
cin >> a >> b;
a--;
b--;
g[a].pb({b, i});
g[b].pb({a, i});
directions[i] = {a, b};
}
tin.resize(n, -1);
up.resize(n, -1);
bridge.resize(m);
for (int i = 0; i < n; i++) {
if (tin[i] == -1) {
dfs1(i, -1);
}
}
timer = 0;
tin.assign(n, 0);
comp.resize(n);
used.assign(n, false);
for (int i = 0; i < n; i++) {
if (tin[i] == 0) {
dfs2(i);
timer++;
}
}
g.clear();
n = timer;
g.assign(n, {});
used.assign(n, false);
for (int i = 0; i < m; i++) {
if (!bridge[i]) {
continue;
}
ll a = comp[directions[i].first], b = comp[directions[i].second];
g[a].pb({b, i});
g[b].pb({a, i});
}
dp.resize(n, vector<ll>(L, -1));
timer = 0;
tin.clear();
tin.assign(n, -1);
tout.resize(n);
pred.resize(n, -1);
pr_edge.resize(n);
limit.resize(n);
for (int i = 0; i < n; i++) {
limit[i] = i;
if (tin[i] == -1) {
dfs3(i, i);
}
}
ll q;
cin >> q;
vector<bool> need_up(n, false), visited(n, false);
while (q--) {
ll x, y;
cin >> x >> y;
x--;
y--;
x = comp[x];
y = comp[y];
if (x == y) {
continue;
}
need_up[x] = true;
ll par = lca(x, y);
if (parent(par, limit[x])) {
limit[x] = par;
}
if (parent(par, limit[y])) {
limit[y] = par;
}
}
// dsu
vector<ll> dsu_pr(n), dsu_sz(n), highest(n);
for (int i = 0; i < n; i++) {
dsu_pr[i] = i;
highest[i] = i;
dsu_sz[i] = 1;
}
function<ll(ll)> lead = [&](ll v) {
if (dsu_pr[v] == v) {
return v;
}
ll r = lead(dsu_pr[v]);
dsu_pr[v] = r;
return r;
};
function<void(ll, ll)> unite = [&](ll v, ll u) {
v = lead(v);
u = lead(u);
if (u == v) {
return;
}
ll new_h;
if (parent(highest[v], highest[u])) {
new_h = highest[v];
} else {
new_h = highest[u];
}
if (dsu_sz[v] < dsu_sz[u]) {
swap(v, u);
}
dsu_pr[u] = v;
dsu_sz[v] += dsu_sz[u];
highest[v] = new_h;
};
// dsu
string answer(m, 'B');
for (int i = 0; i < n; i++) {
if (!visited[i]) {
ll v = i;
ll go_up = limit[v];
while (parent(go_up, v) and go_up != v) {
visited[v] = true;
ll previous = pred[v];
ll a = comp[directions[pr_edge[v]].first];
if (a == v) {
if (need_up[i]) {
answer[pr_edge[v]] = 'R';
} else {
answer[pr_edge[v]] = 'L';
}
} else {
if (need_up[i]) {
answer[pr_edge[v]] = 'L';
} else {
answer[pr_edge[v]] = 'R';
}
}
unite(v, previous);
v = highest[lead(v)];
go_up = limit[v];
}
}
}
cout << answer;
}
int main() {
#ifndef LOCAL
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#else
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cout.precision(30);
ll seed = time(0);
//cerr << "Seed: " << seed << "\n";
srand(seed);
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
