#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9 + 5;
const ll oo = 1e18 + 5;
const int MAXN = 1e5 + 5;
const int LOG = 16;
//#define int ll
int n, m, TimerDFS, low[MAXN], num[MAXN], scc_quanity, scc_id[MAXN], par[MAXN][LOG + 1];
int high[MAXN], f[MAXN];
pair<int, int> edges[MAXN];
vector<pair<int, int>> adj[MAXN];
vector<int> g[MAXN];
bool del[MAXN];
bool vis[MAXN];
stack<int> st;
void DFS_tarjan(int u, int pid) {
++TimerDFS;
st.push(u);
// cout << u << '\n';
num[u] = low[u] = TimerDFS;
for (int i = 0; i < int(adj[u].size()); ++i) {
int v = adj[u][i].first, nid = adj[u][i].second;
if (pid != nid && del[v] == false){
if (num[v] == 0) {
DFS_tarjan(v, nid);
low[u] = min(low[u], low[v]);
} else low[u] = min(low[u], num[v]);
}
}
if (low[u] == num[u]) {
int v;
++scc_quanity;
do {
v = st.top();
del[v] = true;
st.pop();
scc_id[v] = scc_quanity;
} while (v != u);
}
}
void DFS_high(int u, int p) {
for (int i = 0; i < int(g[u].size()); ++i) {
int v = g[u][i];
if (v != p) {
high[v] = high[u] + 1;
par[v][0] = u;
DFS_high(v, u);
}
}
}
void prepare_LCA() {
high[0] = -1;
DFS_high(1, -1);
// for (int j = 1; j <= LOG; ++j) {
// for (int i = 1; i <= n; ++i) {
// par[i][j] = par[par[i][j - 1]][j - 1];
// }
// }
}
//int LCA(int u, int v) {
// if (high[u] < high[v]) return LCA(v, u);
//
// int k = high[u] - high[v];
//
// for (int i = 0; i <= LOG; ++i) {
// if ((k >> i) & 1) {
// u = par[u][i];
// }
// }
//
// if (u == v) return u;
//
// for (int i = LOG; i >= 0; --i) {
// if (par[u][i] != par[v][i]) {
// u = par[u][i];
// v = par[v][i];
// }
// }
// return par[u][0];
//}
void DFS_solve(int u, int p) {
vis[u] = true;
for (int i = 0; i < int(g[u].size()); ++i) {
int v = g[u][i];
if (v != p) {
if (!vis[v])
DFS_solve(v, u);
f[u] += f[v];
}
}
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v; cin >> u >> v;
adj[u].push_back({v, i});
adj[v].push_back({u, i});
edges[i] = {u, v};
}
for (int i = 1; i <= n; ++i)
if (num[i] == 0) DFS_tarjan(i, -1);
// cout << TimerDFS << '\n';
// cout << scc_quanity << '\n';
// for (int i = 1; i <= n; ++i) {
// cout << scc_id[i] << ' ';
// }
// cout << '\n';
for (int i = 1; i <= m; ++i) {
int u = scc_id[edges[i].first], v = scc_id[edges[i].second];
// vi la vo huong nen ko co canh trung
if (u != v) {
g[u].push_back(v);
g[v].push_back(u);
}
}
// for (int i = 1; i <= scc)
// prepare_LCA();
DFS_high(1, -1);
int q; cin >> q;
while (q--) {
int u, v; cin >> u >> v;
u = scc_id[u];
v = scc_id[v];
// int uv = LCA(u, v);
++f[u];
--f[v];
// cout << u << ' ' << v << '\n';
// f[uv] -= 3;
}
for (int i = 1; i <= scc_quanity; ++i)
if (!vis[i])
DFS_solve(i, -1);
for (int i = 1; i <= m; ++i) {
int u = scc_id[edges[i].first], v = scc_id[edges[i].second];
// cout << u << ' ' << v << ' ' << high[u] << ' ' << high[v] << ' ' << f[u] << ' ' << f[v];
if (u == v) {
cout << "B";
} else {
if (high[u] > high[v]) {
if (f[u] >= 1) cout << "R";
else cout << "L";
} else if (f[v] >= 1) cout << "L";
else cout << "R";
}
// cout << '\n';
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
// freopen("oneway.inp", "r", stdin);
// freopen("oneway.out", "w", stdout);
// int T = 1; cin >> T; while(T--)
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
