#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
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; vector<bool> vis;
multiset<int> x; multiset<int> y;
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];
sol[cur.num] = 'B';
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;
for (auto u : mp[v]) {
if (!vis[u]) {
parents[u] = v;
dfsts(u);
}
}
ts.push_back(v);
}
int main() {
cin >> n >> m;
gr.resize(n); sol.resize(m); 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);
for (int i = 0; i < cur_comp; i++) {
if (!vis[i]) {
dfsts(i);
}
}
//cout << "done dfs3" << endl;
cin >> p;
for (int i = 0; i < p; i++) {
int a, b; cin >> a >> b; a--; b--;
if (comp[a] != comp[b]) {
x.insert(comp[a]); y.insert(comp[b]);
}
}
//cout << "taken input " << endl;
for (int i = 0; i < cur_comp; i++) {
if (x.count(ts[i]) > 0) {
x.erase(ts[i]); x.insert(parents[ts[i]]);
sol[translate[{ts[i], parents[ts[i]]}].second] = translate[{ts[i], parents[ts[i]]}].first;
}
if (y.count(ts[i]) > 0) {
y.erase(ts[i]); y.insert(parents[ts[i]]);
sol[translate[{parents[ts[i]], ts[i]}].second] = translate[{parents[ts[i]], ts[i]}].first;
}
while (x.count(parents[ts[i]]) > 0 && y.count(parents[ts[i]]) > 0) {
x.erase(parents[ts[i]]); y.erase(parents[ts[i]]);
}
}
//cout << "part 4" << endl;
for (int i = 0; i < sol.size(); i++) {
cout << sol[i];
}
cout << "\n";
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:154:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for (int i = 0; i < sol.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
