#include <bits/stdc++.h>
#define pb push_back
#define LINE "----------------------------\n"
using namespace std;
using PII = pair <int, int>;
using VI = vector <int>;
const int N = 1e5 + 5;
int n, m, q;
vector <PII> paths[N];
vector <VI> edges;
string answ = ".LRB";
int par[N], dp[N], dp1[N], ans[N];
int find(int a) {
if (par[a] == a) return a;
return par[a] = find(par[a]);
}
void merge(int a, int b) {
a = find(a);
b = find(b);
par[b] = a;
}
bool vis[N], vis1[N];
int dfs(int pos, int p, int par = 0) {
vis[pos] = 1;
vis1[p] = 1;
vector <int> curChildren;
for (auto&[a, b] : paths[pos]) {
if (vis1[b]) continue;
if (vis[a]) {
dp[pos]++;
dp[a]--;
vis1[b] = 1;
continue;
}
curChildren.pb(a);
dp[pos] += dfs(a, b, pos);
}
if (dp[pos] > 0) merge(pos, par);
for (auto&a : curChildren) {
dp1[pos] += dp1[a];
}
for (auto&[a, b] : paths[pos])
if (find(a) == find(pos)) ans[b] |= 3;
if (p > 0) {
VI curEdge = {pos, par, p};
// cout << LINE;
// cout << "curEdge: " << pos << ' ' << par << ' ' << p << '\n';
// cout << "edge: " << edges[p][0] << ' ' << edges[p][1] << ' ' << edges[p][2] << '\n';
// cout << dp1[pos] << ' ' << ans[p] << '\n';
if (dp1[pos] == 0) ans[p] |= 3;
ans[p] |= ((curEdge == edges[p]) == (dp1[pos] > 0) ? 2 : 1);
}
return dp[pos];
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("0.in", "r", stdin);
// freopen("0.out", "w", stdout);
cin >> n >> m;
edges.pb({0, 0, 0});
for (int i = 1; i <= m; i++) {
int a, b; cin >> a >> b;
edges.pb({a, b, i});
paths[a].pb({b, i});
paths[b].pb({a, i});
}
cin >> q;
for (int i = 1; i <= q; i++) {
int a, b;
cin >> a >> b;
dp1[a]++;
dp1[b]--;
}
iota(par+1, par+1+n, 1);
dfs(1, 0);
// cout << LINE;
// for (int i = 1; i <= n; i++) cout << i << ": " << find(i) << '\n';
for (int i = 1; i <= m; i++) cout << answ[ans[i]]; cout << '\n';
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:82:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
82 | for (int i = 1; i <= m; i++) cout << answ[ans[i]]; cout << '\n';
| ^~~
oneway.cpp:82:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
82 | for (int i = 1; i <= m; i++) cout << answ[ans[i]]; cout << '\n';
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
