#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mx = 2e5+5;
int n, m, q;
vector<int> g[mx];
int dfn[mx], low[mx];
int ans[mx];
int pe[mx];
int t;
bool vis[mx], vise[mx];
vector<int> ng[mx];
int a[mx];
int dep[mx];
struct Edge {
int u, v;
int id;
} e[mx];
void print(int a[], int n) {
for (int i=1;i<=n;i++) {
cout << a[i] << " ";
}
cout << "\n";
}
void pt() {
print(dep, n);
print(ans, m);
print(a, n);
}
void dfs1(int x, int peg, int d) {
low[x] = dfn[x] = ++t;
pe[x] = peg;
vis[x] = 1;
dep[x] = d;
for (int i:g[x]) {
if (vise[i]) continue;
vise[i] = 1;
auto [u, v, id] = e[i];
if (u != x) swap(u, v);
if (!vis[v]) {
ng[u].push_back(v);
ng[v].push_back(u);
dfs1(v, i, d+1);
low[u] = min(low[u], low[v]);
} else {
low[u] = min(low[u], dfn[v]);
}
}
if (low[x] != dfn[x]) {
ans[peg] = 3;
}
}
void dfs2(int x, int p) {
for (int i:ng[x]) {
if (i == p) continue;
dfs2(i, x);
a[x] += a[i];
}
if (ans[pe[x]] == 3) return;
auto [u, v, id] = e[pe[x]];
if (a[x] > 0) {
if (dep[u] > dep[v]) {
ans[id] = 1;
} else {
ans[id] = 2;
}
} else if (a[x] < 0) {
if (dep[u] < dep[v]) {
ans[id] = 1;
} else {
ans[id] = 2;
}
}
}
signed main() {
cin.tie(0);ios::sync_with_stdio(0);
cin >> n >> m;
for (int i=1;i<=m;i++) {
int u, v;
cin >> u >> v;
g[u].push_back(i);
g[v].push_back(i);
e[i] = {u, v, i};
}
for (int i=1;i<=n;i++) {
if (!vis[i]) {
dfs1(i, 0, 1);
}
}
cin >> q;
while (q--) {
int u, v;
cin >> u >> v;
a[u]++;
a[v]--;
}
for (int i=1;i<=n;i++) {
vis[i] = 0;
}
for (int i=1;i<=n;i++) {
if (!vis[i]) {
dfs2(i, 0);
}
}
for (int i=1;i<=m;i++) {
if (ans[i] == 3 or ans[i] == 0) {
cout << 'B';
} else if (ans[i] == 1) {
cout << 'R';
} else {
cout << 'L';
}
}
cout << "\n";
}
Compilation message
oneway.cpp: In function 'void dfs1(long long int, long long int, long long int)':
oneway.cpp:43:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
43 | auto [u, v, id] = e[i];
| ^
oneway.cpp: In function 'void dfs2(long long int, long long int)':
oneway.cpp:66:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
66 | auto [u, v, id] = e[pe[x]];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
19804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
19804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
19804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
