#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
typedef pair <int,int> pii;
const ll N = 1e5 + 5;
const ll S = 2010;
const ll LOG_N = 18;
const ll oo = 1e16+7;
const ll mod = 2e9 + 7;
char ans[N];
pii edges[N];
vector <vector<pii>> bridge_tree;
int up[N], down[N];
int tin[N], tout[N];
int st[N][20];
int cnt = 0;
struct tarjan_tree {
int n;
vector<vector<int>> comps;
vector<vector<pii>> g;
vector<pair<pii, int>> bridge;
vector<int> id, art;
tarjan_tree(int n) : n(n), g(n+1), id(n+1), art(n+1) {}
void add_edge(vector<vector<pii>> &g, int u, int v, int idx) { /// nodes from [1, n]
g[u].push_back({v, idx});
g[v].push_back({u, idx});
}
void add_edge(int u, int v, int idx) { add_edge(g, u, v, idx); }
void tarjan(bool with_bridge) {
vector<int> dfn(n+1), low(n+1);
stack<int> st;
comps.clear();
function<void(int, int, int&)> dfs = [&](int u, int p, int &t) {
dfn[u] = low[u] = ++t;
st.push(u);
int cntp = 0;
for(auto [v, idx] : g[u]) {
cntp += v == p;
if(!dfn[v]) {
dfs(v, u, t);
low[u] = min(low[u], low[v]);
if(with_bridge && low[v] > dfn[u]) {
bridge.push_back(make_pair(make_pair(min(u,v), max(u,v)), idx));
comps.push_back({});
for(int w = -1; w != v; )
comps.back().push_back(w = st.top()), st.pop();
}
if(!with_bridge && low[v] >= dfn[u]) {
art[u] = (dfn[u] > 1 || dfn[v] > 2);
comps.push_back({u});
for(int w = -1; w != v; )
comps.back().push_back(w = st.top()), st.pop();
}
}
else if(v != p || cntp > 1) low[u] = min(low[u], dfn[v]);
}
if(p == -1 && ( with_bridge || g[u].size() == 0 )) {
comps.push_back({});
for(int w = -1; w != u; )
comps.back().push_back(w = st.top()), st.pop();
}
};
for(int u = 1, t; u <= n; ++u)
if(!dfn[u]) dfs(u, -1, t = 0);
}
vector<vector<pii>> build_bridge_tree() {
tarjan(true);
vector<vector<pii>> tree(comps.size());
for(int i = 0; i < comps.size(); ++i)
for(int u : comps[i]) id[u] = i;
for(auto &b : bridge)
add_edge(tree, id[b.ff.ff], id[b.ff.ss], b.ss);
return tree;
}
};
void dfs (int u, int p) {
st[u][0] = p;
tin[u] = cnt++;
for (auto &v : bridge_tree[u]) {
if (v.ff == p) continue;
dfs(v.ff, u);
}
tout[u] = cnt - 1;
}
bool anc (int u, int v) {
if (tin[u] <= tin[v] && tout[v] <= tout[u]) return true;
return false;
}
int lca (int u, int v) {
if (anc(u, v)) return u;
for (int i = 19; i >= 0; --i) {
if (!anc(st[u][i], v))
u = st[u][i];
}
return st[u][0];
}
void solve (int u, int p, int id) {
for (auto &v : bridge_tree[u]) {
if (v.ff == p) continue;
solve (v.ff, u, v.ss);
up[u] += up[v.ff];
down[u] += down[v.ff];
}
assert(up[u] == 0 || down[u] == 0);
if (up[u]) {
if (u == edges[id].ff) ans[id] = 'R';
else ans[id] = 'L';
}
if (down[u]) {
if (p == edges[id].ff) ans[id] = 'R';
else ans[id] = 'L';
}
}
int main () {
#ifdef LOCAL
freopen("input.txt","r",stdin);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m, p;
cin >> n >> m;
tarjan_tree tj(n);
for (int i = 0; i < m; ++i) {
int a, b; cin >> a >> b;
ans[i] = 'B';
if (a == b) {
continue;
}
else {
tj.add_edge(a, b, i);
edges[i] = {a, b};
}
}
bridge_tree = tj.build_bridge_tree();
dfs(0,0);
int nn = bridge_tree.size();
for (int i = 1; i < 20; ++i) {
for (int j = 0; j < nn; ++j) {
st[j][i] = st[st[j][i-1]][i-1];
}
}
cin >> p;
for (int i = 0; i < p; ++i) {
int u, v; cin >> u >> v;
u = tj.id[u], v = tj.id[v];
int lc = lca(u, v);
//cout << u << " " << v << " " << lc << '\n';
up[u]++;
up[lc]--;
down[v]++;
down[lc]--;
}
for (int i = 0; i < m; ++i) {
edges[i].ff = tj.id[edges[i].ff];
edges[i].ss = tj.id[edges[i].ss];
}
solve(0,0,-1);
for (int i = 0; i < m; ++i) {
cout << ans[i];
}
return 0;
}
Compilation message
oneway.cpp: In lambda function:
oneway.cpp:45:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
45 | for(auto [v, idx] : g[u]) {
| ^
oneway.cpp: In member function 'std::vector<std::vector<std::pair<int, int> > > tarjan_tree::build_bridge_tree()':
oneway.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i = 0; i < comps.size(); ++i)
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
