#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
int n, m, q;
int p[N], ans[N];
vector<pair<int, int>> g[N];
vector<pair<int, int>> g2[N];
int num[N], low[N], tt;
int par[N], parid[N], dep[N];
vector<tuple<int, int, int>> tr;
int getp(int u) {
if (p[u] == u) {
return u;
} else {
return p[u] = getp(p[u]);
}
}
void mrg(int u, int v) {
p[getp(v)] = getp(u);
}
void dfs(int u, int pid) {
num[u] = low[u] = ++tt;
for (auto e : g[u]) {
int v, id; tie(v, id) = e;
if (id + pid) {
if (num[v]) low[u] = min(low[u], num[v]);
else {
dfs(v, id);
low[u] = min(low[u], low[v]);
if (low[v] > num[u]) {
tr.emplace_back(u, v, id);
} else mrg(u, v);
}
}
}
}
void dfs2(int u, int p) {
for (auto e : g2[u]) {
int v, id; tie(v, id) = e;
if (v ^ p) {
par[v] = u;
parid[v] = -id;
dep[v] = dep[u] + 1;
dfs2(v, u);
}
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) p[i] = i;
for (int i = 1; i <= m; ++i) {
int u, v;
scanf("%d %d", &u, &v);
g[u].emplace_back(v, i);
g[v].emplace_back(u, -i);
}
dfs(1, 0);
for (auto e : tr) {
int u, v, id; tie(u, v, id) = e;
u = getp(u), v = getp(v);
g2[u].emplace_back(v, id);
g2[v].emplace_back(u, -id);
}
dfs2(1, 0);
scanf("%d", &q);
while (q--) {
int u, v;
scanf("%d %d", &u, &v);
u = getp(u), v = getp(v);
while (u ^ v) {
if (dep[u] > dep[v]) {
if (parid[u] > 0) ans[parid[u]] = 1;
else ans[-parid[u]] = 2;
mrg(par[u], u);
u = getp(u);
} else {
if (parid[v] > 0) ans[parid[v]] = 2;
else ans[-parid[v]] = 1;
mrg(par[v], v);
v = getp(v);
}
}
}
for (int i = 1; i <= m; ++i) {
if (ans[i] == 0) putchar('B');
else if (ans[i] == 1) putchar('L');
else putchar('R');
}
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:57:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:61:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:73:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
oneway.cpp:76:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3016 ms |
4992 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3016 ms |
4992 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3016 ms |
4992 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
