#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <algorithm>
using namespace std;
int n, m, p;
int INF = 2 * 1e9;
vector<vector<int>> gr;
vector<bool> used;
vector<int> comp; vector<vector<int>> cgr;
vector<int> d, dp;
vector<char> sol;
set<pair<int, int>> done;
vector<vector<int>> mp;
vector<int> bridges;
vector<int> ts, depth, changesx, changesy; vector<bool> vis;
vector<vector<int>> bj;
map<pair<int, int>, pair<char, int>> translate;
vector<int> parents;
struct Edge {
int from, to, num; bool is_bridge;
Edge() {}
Edge(int from, int to, int num) : from(from), to(to), num(num), is_bridge(false) {}
};
vector<Edge> edges;
void dfs(int v, int pnum = -1, int p = -1) {
used[v] = true;
if (p == -1) {
d[v] = 0;
}
else {
d[v] = d[p] + 1;
}
dp[v] = INF;
for (auto e : gr[v]) {
Edge cur = edges[e];
if (!used[cur.to]) {
dfs(cur.to, cur.num, v); dp[v] = min(dp[v], dp[cur.to]);
}
else if (pnum != cur.num) {
dp[v] = min(dp[v], d[cur.to]);
}
}
if (pnum != -1 && dp[v] >= d[v]) {
edges[2 * pnum].is_bridge = true; edges[2 * pnum + 1].is_bridge = true;
bridges.push_back(pnum);
}
}
void dfs2(int v, int cur_comp) {
comp[v] = cur_comp;
for (auto e : gr[v]) {
Edge cur = edges[e];
if (!cur.is_bridge && comp[cur.to] == -1) {
dfs2(cur.to, cur_comp);
}
else if (comp[cur.to] != -1 && cur.is_bridge) {
cgr[cur_comp].push_back(comp[cur.to]); cgr[comp[cur.to]].push_back(cur_comp);
}
}
}
void dfsts(int v) {
vis[v] = true;
if (parents[v] == v) {
depth[v] = 0;
}
else {
depth[v] = 1 + depth[parents[v]];
}
for (auto u : mp[v]) {
if (!vis[u]) {
parents[u] = v;
dfsts(u);
}
}
ts.push_back(v);
}
int LCA(int a, int b) {
if (a == b) {
return a;
}
if (bj[a][0] == bj[b][0]) {
return bj[a][0];
}
int l = 0; int h = 17;
while (l + 1 < h) {
int m = (l + h) / 2;
if (bj[a][m] == bj[b][m]) {
h = m;
}
else {
l = m;
}
}
return LCA(bj[a][l], bj[b][l]);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
gr.resize(n); sol.assign(m, 'B'); d.resize(n); dp.resize(n);
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b; a--; b--;
edges.push_back(Edge(a, b, i)); edges.push_back(Edge(b, a, i));
gr[a].push_back(2 * i); gr[b].push_back(2 * i + 1);
}
used.assign(n, false);
for (int i = 0; i < n; i++) {
if (!used[i]) {
dfs(i);
}
}
//cout << "done dfs1" << endl;
comp.resize(n, -1); int cur_comp = 0;
for (int i = 0; i < n; i++) {
if (comp[i] == -1) {
cgr.push_back(vector<int>()); dfs2(i, cur_comp++);
}
}
//cout << "done dfs2 " << endl;
mp.resize(cur_comp);
for (int bridge : bridges) {
mp[comp[edges[2*bridge].from]].push_back(comp[edges[2*bridge].to]);
mp[comp[edges[2*bridge].to]].push_back(comp[edges[2*bridge].from]);
translate[{comp[edges[2 * bridge].from], comp[edges[2 * bridge].to]}] = { 'R', bridge };
translate[{comp[edges[2 * bridge].to], comp[edges[2 * bridge].from]}] = { 'L', bridge };
}
vis.assign(cur_comp, false); parents.resize(cur_comp); depth.resize(cur_comp, INF);
for (int i = 0; i < cur_comp; i++) {
if (!vis[i]) {
parents[i] = i; dfsts(i);
}
}
bj.resize(cur_comp, vector<int>(18));
for (int i = 0; i < cur_comp; i++) {
bj[i][0] = parents[i];
}
for (int i = 1; i < 18; i++) {
for (int j = 0; j < cur_comp; j++) {
bj[j][i] == bj[bj[j][i - 1]][i - 1];
}
}
//cout << "done dfs3" << endl;
changesx.resize(cur_comp, -1); changesy.resize(cur_comp, -1);
/*
for (int i = 0; i < n; i++) {
cout << "element " << i + 1 << " has component " << comp[i] << endl;
}
for (int i = 0; i < cur_comp; i++) {
cout << "depth of comp " << i << " is " << depth[i] << endl;
}
*/
cin >> p;
for (int i = 0; i < p; i++) {
int a, b; cin >> a >> b; a--; b--;
//cout << "components " << comp[a] << " " << comp[b] << endl;
if (comp[a] != comp[b]) {
int lca = LCA(comp[a], comp[b]); //cout << "lca for a, b = " << a + 1 << " " << b + 1 << " of component " << comp[a] << " " << comp[b] << " is " << lca << endl;
if (changesx[comp[a]] == -1) {
changesx[comp[a]] = lca;
}
else if (depth[lca] < depth[changesx[comp[a]]]) {
changesx[comp[a]] = lca;
}
if (changesy[comp[b]] == -1){
changesy[comp[b]] = lca;
}
else if (depth[lca] < depth[changesy[comp[b]]]) {
changesy[comp[b]] = lca;
}
}
}
// now we need to do the changing
for (int i = 0; i < cur_comp; i++) {
//cout << "ts[i] and changes are " << ts[i] << " " << changesx[ts[i]] << " " << changesy[ts[i]] << endl;
if (changesx[ts[i]] != -1) {
if (depth[ts[i]] != depth[changesx[ts[i]]]) {
sol[translate[{ts[i], parents[ts[i]]}].second] = translate[{ts[i], parents[ts[i]]}].first;
if (changesx[parents[ts[i]]] == -1) {
changesx[parents[ts[i]]] = changesx[ts[i]];
}
else if (depth[changesx[ts[i]]] < depth[changesx[parents[ts[i]]]]) {
changesx[parents[ts[i]]] = changesx[ts[i]];
}
}
}
if (changesy[ts[i]] != -1) {
if (depth[ts[i]] != depth[changesy[ts[i]]]) {
sol[translate[{parents[ts[i]], ts[i]}].second] = translate[{parents[ts[i]], ts[i]}].first;
if (changesy[parents[ts[i]]] == -1) {
changesy[parents[ts[i]]] = changesy[ts[i]];
}
else if (depth[changesy[ts[i]]] < depth[changesy[parents[ts[i]]]]) {
changesy[parents[ts[i]]] = changesy[ts[i]];
}
}
}
}
//cout << "taken input " << endl;
/*
cout << "num components " << cur_comp << endl;
for (int i = 0; i < n; i++) {
cout << "comp " << i << " = " << comp[i] << endl;
}
*/
for (int i = 0; i < sol.size(); i++) {
cout << sol[i];
}
cout << "\n";
}
/*
for (int i = 0; i < cur_comp; i++) {
//cout << "ts[" << i << "] = " << ts[i] << " with a parent of " << parents[ts[i]] << " with a count of " << x.count(ts[i]) << " for x and " << y.count(ts[i]) << " for y" << endl;
//cout << "num occurentces " << x.count(ts[i]) << " " << y.count(ts[i]) << endl;
int xcount = x.count(ts[i]); int ycount = y.count(ts[i]);
for (int i = 0; i < min(xcount, ycount); i++) {
//cout << "count2 " << x.count(ts[i]) << endl;
auto ix = x.find(ts[i]); x.erase(ix);
auto iy = y.find(ts[i]); y.erase(iy);
}
xcount = x.count(ts[i]); ycount = y.count(ts[i]);
for (int i = 0; i < xcount; i++) {
//cout << "count " << x.count(ts[i]) << endl;
x.insert(parents[ts[i]]);
}
if (xcount > 0) {
//cout << "i = " << i << " ts[i] = " << ts[i] << " and x.count(ts[i] = " << x.count(ts[i]) << endl;
x.erase(ts[i]); sol[translate[{ts[i], parents[ts[i]]}].second] = translate[{ts[i], parents[ts[i]]}].first;
//cout << "x changing " << translate[{ts[i], parents[ts[i]]}].second << " index to " << translate[{ts[i], parents[ts[i]]}].first << endl;
}
//cout << "occ of y " << y.count(ts[i]) << endl;
for (int i = 0; i < ycount; i++) {
//cout << "yoyoyo" << endl;
y.insert(parents[ts[i]]); //cout << "adding " << endl;
}
if (ycount > 0) {
//cout << "hello " << endl;
y.erase(ts[i]); sol[translate[{parents[ts[i]], ts[i]}].second] = translate[{parents[ts[i]], ts[i]}].first;
//cout << "y changing " << translate[{parents[ts[i]], ts[i]}].second << " index to " << translate[{parents[ts[i]], ts[i]}].first << endl;
}
//cout << "parents count of " << ts[i] << " " << x.count(parents[ts[i]]) << " " << y.count(parents[ts[i]]) << endl;
}
//cout << "part 4" << endl;
*/
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:160:13: warning: value computed is not used [-Wunused-value]
160 | bj[j][i] == bj[bj[j][i - 1]][i - 1];
oneway.cpp:237:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
237 | for (int i = 0; i < sol.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
856 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
856 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
856 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
