#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define repn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef vector<vpi> vvpi;
template<class t> t setmax(t& a, t& b) {if (a < b) return a = b; return a;}
template<class t> t setmin(t& a, t& b) {if (a < b) return a; return a = b;}
const int maxn = 1e5;
int n, m;
vvpi gp, gp2;
vvi comp;
int id[maxn], vis[maxn], num[maxn], low[maxn], bridge[maxn], tc;
int tin[maxn], tout[maxn], par[maxn][20];
void tarjan(int u, int pi = -1) {
vis[u] = 1;
low[u] = num[u] = tc++;
for (auto[v, i] : gp[u]) {
if (i == pi) continue;
if (vis[v] == 1) {
setmin(low[u], num[v]);
} else if (vis[v] == 0) {
tarjan(v, i);
setmin(low[u], low[v]);
if (low[v] > num[u]) bridge[i] = true;
}
}
vis[u] = 2;
}
int pari[maxn];
void dfs(int u) {
vis[u] = true;
comp.back().pb(u);
for (auto[v, i] : gp[u]) {
if (vis[v]) continue;
if (bridge[i]) continue;
dfs(v);
}
}
void prelca(int u, int p, int pi = -1) {
pari[u] = pi;
vis[u] = true;
tin[u] = tc++;
par[u][0] = p;
for (int i = 1; i < 20; i++) par[u][i] = par[par[u][i-1]][i-1];
for (auto[v, i] : gp2[u]) {
if (v == p) continue;
prelca(v, u, i);
}
tout[u] = tc++;
}
bool isanc(int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; }
int LCA(int a, int b) {
if (isanc(a, b)) return a;
if (isanc(b, a)) return b;
for (int i = 19; i >= 0; i--) {
if (!isanc(par[a][i], b)) a = par[a][i];
}
return par[a][0];
}
int ver[maxn], var[maxn];
void dfs2(int u, int p = -1) {
vis[u] = true;
for (auto[v, i] : gp2[u]) {
if (v == p) continue;
dfs2(v, u);
ver[u] += ver[v];
var[u] += var[v];
}
}
void solve() {
cin >> n >> m;
gp = vvpi(n);
vpi edg;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--, v--;
edg.pb({u, v});
gp[u].pb({v, i});
gp[v].pb({u, i});
}
fill(vis, vis+n, 0);
fill(bridge, bridge+m, 0);
tc = 0;
for (int u = 0; u < n; u++) {
if (!vis[u]) tarjan(u);
}
comp.clear();
fill(vis, vis+n, 0);
for (int u = 0; u < n; u++) {
if (!vis[u]) {
comp.pb(vi());
dfs(u);
}
}
int last = 0;
for (vi v : comp) {
for (int x : v) {
id[x] = last;
}
last++;
}
gp2 = vvpi(n);
for (int i = 0; i < m; i++) {
if (bridge[i]) {
int u = id[edg[i].ff];
int v = id[edg[i].ss];
gp2[u].pb({v, i});
gp2[v].pb({u, i});
}
}
tc = 0;
fill(vis, vis+n, 0);
for (int u = 0; u < n; u++) {
if (!vis[u]) prelca(u, u);
}
// for (int u = 0; u < last; u++) {
// cout << u+1 << ": ";
// for (auto[x, i] : gp2[u]) cout << x+1 << " ";
// cout << endl;
// }
fill(ver, ver+n, 0);
fill(var, var+n, 0);
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int a, b;
cin >> a >> b;
a--, b--;
a = id[a];
b = id[b];
int lca = LCA(a, b);
// cout << a+1 << " " << b+1 << " " << lca+1 << endl;
ver[a]++;
ver[lca]--;
var[b]++;
var[lca]--;
}
dfs2(0);
string ans(m, 'B');
for (int u = 1; u < n; u++) {
int i = pari[u];
int p = par[u][0];
if (ver[u]) {
// cout << u+1 << " " << p+1 << endl;
if (pii{u, p} == pii{id[edg[i].ff], id[edg[i].ss]}) ans[i] = 'R';
else ans[i] = 'L';
} else if (var[u]) {
// cout << p+1 << " " << u+1 << endl;
if (pii{p, u} == pii{id[edg[i].ff], id[edg[i].ss]}) ans[i] = 'R';
else ans[i] = 'L';
}
}
cout << ans << endl;
}
int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(null);
// cout.tie(null);
// freopen("milkorder.out", "w", stdout);
// freopen("milkorder.in", "r", stdin);
ll t = 1;
// scanf("%d", &t);
while (t--) solve();
}
Compilation message
oneway.cpp: In function 'void tarjan(int, int)':
oneway.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
30 | for (auto[v, i] : gp[u]) {
| ^
oneway.cpp: In function 'void dfs(int)':
oneway.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
48 | for (auto[v, i] : gp[u]) {
| ^
oneway.cpp: In function 'void prelca(int, int, int)':
oneway.cpp:61:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
61 | for (auto[v, i] : gp2[u]) {
| ^
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:81:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
81 | for (auto[v, i] : gp2[u]) {
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
4 ms |
8792 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
4 ms |
8792 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
4 ms |
8792 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
