#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 e = 2.718281828459;
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;
};
void solve() {
ll n, m;
cin >> n >> m;
vector<vector<edge>> g(n);
vector<pair<ll, ll>> directions(m);
vector<bool> used(n);
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};
}
vector<ll> tin(n, -1), up(n, -1);
vector<bool> bridge(m);
ll timer = 0;
function<void(ll, ll)> 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);
up[v] = min(up[v], up[e.u]);
if (up[e.u] > tin[v]) {
bridge[e.ind] = true;
}
}
};
for (int i = 0; i < n; i++) {
if (!used[i]) {
dfs1(i, -1);
}
}
timer = 0;
tin.assign(n, 0);
vector<ll> comp(n);
used.assign(n, false);
function<void(ll)> dfs2 = [&](ll v) {
comp[v] = timer;
used[v] = true;
for (auto e : g[v]) {
if (used[e.u] or bridge[e.ind]) {
continue;
}
dfs2(e.u);
}
};
for (int i = 0; i < n; i++) {
if (!used[i]) {
dfs2(i);
timer++;
}
}
g.clear();
n = timer;
g.assign(n, {});
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});
}
ll L = 20;
vector<vector<ll>> dp(n, vector<ll>(L, -1));
timer = 0;
tin.clear();
tin.assign(n, -1);
used.assign(n, false);
vector<ll> tout(n), pred(n, -1), pr_edge(n), limit(n);
function<void(ll, ll)> dfs3 = [&](ll v, ll pr) {
tin[v] = timer;
timer++;
dp[v][0] = pr;
used[v] = true;
for (int i = 1; i < L; i++) {
dp[v][i] = dp[dp[v][i - 1]][i - 1];
}
for (auto e : g[v]) {
if (e.u != pr) {
pred[e.u] = v;
pr_edge[e.u] = e.ind;
dfs3(e.u, v);
}
}
tout[v] = timer;
timer++;
};
for (int i = 0; i < n; i++) {
limit[i] = i;
if (!used[i]) {
dfs3(i, i);
}
}
function<bool(ll, ll)> parent = [&](ll v, ll u) {
return (tin[v] <= tin[u] and tout[v] >= tout[u]);
};
function<ll(ll, 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];
};
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)];
if (parent(limit[v], go_up)) {
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 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
512 KB |
Output is correct |
| 4 |
Correct |
4 ms |
768 KB |
Output is correct |
| 5 |
Correct |
3 ms |
768 KB |
Output is correct |
| 6 |
Correct |
3 ms |
512 KB |
Output is correct |
| 7 |
Correct |
3 ms |
768 KB |
Output is correct |
| 8 |
Correct |
3 ms |
640 KB |
Output is correct |
| 9 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
512 KB |
Output is correct |
| 4 |
Correct |
4 ms |
768 KB |
Output is correct |
| 5 |
Correct |
3 ms |
768 KB |
Output is correct |
| 6 |
Correct |
3 ms |
512 KB |
Output is correct |
| 7 |
Correct |
3 ms |
768 KB |
Output is correct |
| 8 |
Correct |
3 ms |
640 KB |
Output is correct |
| 9 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
512 KB |
Output is correct |
| 4 |
Correct |
4 ms |
768 KB |
Output is correct |
| 5 |
Correct |
3 ms |
768 KB |
Output is correct |
| 6 |
Correct |
3 ms |
512 KB |
Output is correct |
| 7 |
Correct |
3 ms |
768 KB |
Output is correct |
| 8 |
Correct |
3 ms |
640 KB |
Output is correct |
| 9 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
