#include <bits/stdc++.h>
using namespace std;
vector < int > E[100001], TE[100001];
int n, m, p;
pair < int, int > edges[100001], pairs[100001];
vector < int > order;
int fa[100001], vi[100001], dep[100001], covered[100001], com[100001], C, fa2[100001], dep2[100001], J2[17][100001], JC[17][100001];
void DFS(int p, int f, int d)
{
vi[p] = 1;
fa[p] = f;
dep[p] = d;
order.push_back(p);
for (int v : E[p])
if (!vi[v])
DFS(v, p, d + 1);
else if (dep[v] < dep[p])
{
covered[p]++;
covered[v]--;
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &edges[i].first, &edges[i].second);
E[edges[i].first].push_back(edges[i].second);
E[edges[i].second].push_back(edges[i].first);
}
scanf("%d", &p);
for (int i = 1; i <= p; i++)
scanf("%d%d", &pairs[i].first, &pairs[i].second);
DFS(1, 0, 0);
for (auto it = order.rbegin(); *it != 1; it++)
covered[fa[*it]] += covered[*it];
for (int u : order)
if (u == 1 || covered[u] == 1)
com[u] = ++C;
else
com[u] = com[fa[u]];
for (int i = 2; i <= n; i++)
if (com[i] != com[fa[i]])
{
fa2[com[i]] = com[fa[i]];
dep2[com[i]] = dep2[com[fa[i]]] + 1;
}
for (int i = 1; i <= C; i++)
J2[0][i] = fa2[i];
for (int i = 1; i <= 16; i++)
for (int j = 1; j <= C; j++)
J2[i][j] = J2[i - 1][J2[i - 1][j]];
for (int i = 1; i <= p; i++)
{
int u = com[pairs[i].first], v = com[pairs[i].second];
for (int j = 16; j >= 0; j--)
{
if (dep2[u] - dep2[v] >= 1 << j)
{
JC[j][u] |= 1;
u = J2[j][u];
}
if (dep2[v] - dep2[u] >= 1 << j)
{
JC[j][v] |= 2;
v = J2[j][v];
}
}
if (u == v)
continue;
for (int j = 16; j >= 0; j--)
if (J2[j][u] != J2[j][v])
{
JC[j][u] |= 1;
u = J2[j][u];
JC[j][v] |= 2;
v = J2[j][v];
}
JC[0][u] |= 1;
JC[0][v] |= 2;
}
for (int i = 16; i; i--)
for (int j = 1; j <= C; j++)
if (JC[i][j])
{
JC[i - 1][j] |= JC[i][j];
JC[i - 1][J2[i - 1][j]] |= JC[i][j];
}
for (int i = 1; i <= m; i++)
{
int u = com[edges[i].first], v = com[edges[i].second], swapped = 0;
if (u == v)
putchar('B');
else
{
if (dep2[u] > dep2[v])
{
swap(u, v);
swapped = 1;
}
putchar(JC[0][v] == 0 ? 'B' : ((JC[0][v] == 1) != swapped ? 'L' : 'R'));
}
}
puts("");
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
28 | scanf("%d%d", &edges[i].first, &edges[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
32 | scanf("%d", &p);
| ~~~~~^~~~~~~~~~
oneway.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | scanf("%d%d", &pairs[i].first, &pairs[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
18268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
18268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
18268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
