#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
#define ld long double
using namespace std;
int n, m;
vector<vector<pii> > graph;
vector<int> disc;
vector<int> low;
vector<pii> par;
vector<bool> visited;
vector<bool> normal;
vector<bool> bridge;
vector<vector<pii> > tree;
int timer = 0;
void dfs(int v, int p = -1) {
visited[v] = true;
disc[v] = low[v] = timer++;
sort(graph[v].begin(), graph[v].end());
for (int i = 0; i < graph[v].size(); i++) {
int curr = graph[v][i].first;
int edgenum = graph[v][i].second;
if (i != 0 && curr == graph[v][i - 1].first) {
bridge[edgenum] = false;
continue;
}
if (curr == p)
continue;
else if (visited[curr])
low[v] = min(low[v], disc[curr]);
else {
dfs(curr, v);
tree[curr].push_back({v, edgenum});
tree[v].push_back({curr, edgenum});
low[v] = min(low[v], low[curr]);
if (low[curr] > disc[v])
bridge[edgenum] = true;
}
}
}
void dfs2(int v, int p = -1) {
for (pii x : tree[v]) {
if (x.first != p)
{
par[x.first] = pii(v, x.second);
dfs2(x.first, v);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
freopen("fout.txt", "w", stdout);
cin >> n >> m;
graph.resize(n + 1, vector<pii>());
visited.resize(n + 1, false);
disc.resize(n + 1, 1e9);
low.resize(n + 1, 1e9);
normal.resize(m + 1, false);
bridge.resize(m + 1, false);
par.resize(n + 1, pii(-1, -1));
tree.resize(n + 1, vector<pii>());
for (int i = 0; i < m; i++) {
int f, t;
cin >> f >> t;
if (f < t)
normal[i] = true;
graph[f].push_back({t, i});
graph[t].push_back({f, i});
}
for (int i = 1; i <= n; i++) {
if (!visited[i])
dfs(i);
}
string out = "";
for (int i = 0; i < m; i++)
out += 'B';
int p;
cin >> p;
while (p--) {
int f; pii t(0, 0);
cin >> f >> t.first;
dfs2(f);
par[f] = pii(-1, -1);
pii s = par[t.first];
while (s.first != -1) {
if (bridge[s.second]) {
if (normal[s.second]) {
if (s.first < t.first)
out[s.second] = 'R';
else
out[s.second] = 'L';
}
else {
if (s < t)
out[s.second] = 'L';
else
out[s.second] = 'R';
}
}
pii temp = s;
s = par[s.first];
t = temp;
}
}
cout << out << "\n";
}
Compilation message
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for (int i = 0; i < graph[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | freopen("fout.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
