#include <bits/stdc++.h>
using namespace std;
const int N = (int) 1e5 + 7;
const int K = 20;
vector<int> g[N], g2[N];
int n, m, q, sumEdge[N], dep[N], mindep[N], xx[N], yy[N], ff[N], ss[N], top, lg2[2 * N], par[N], sol[N];
pair<int, int> rmq[K][2 * N];
bool isBridge[N];
bool vis[N];
int color[N], currentColor;
map<pair<int, int>, int> coresp;
void dfs_build_bridges(int a, int parrent_edge_id = 0) {
mindep[a] = dep[a];
vector<int> downEdges;
for (auto &i : g[a]) {
int b = sumEdge[i] - a;
if (dep[b] == -1) {
dep[b] = 1 + dep[a];
dfs_build_bridges(b, i);
mindep[a] = min(mindep[a], mindep[b]);
downEdges.push_back(i);
continue;
}
if (i == parrent_edge_id) {
continue;
}
mindep[a] = min(mindep[a], dep[b]);
}
for (auto &i : downEdges) {
int b = sumEdge[i] - a;
if (dep[a] < mindep[b]) {
isBridge[i] = 1;
}
}
}
void dfsColor(int a) {
color[a] = currentColor;
for (auto &i : g[a]) {
int b = sumEdge[i] - a;
if (isBridge[i]) {
if (color[b]) {
coresp[{color[a], color[b]}] = i;
coresp[{color[b], color[a]}] = i;
g2[color[a]].push_back(color[b]);
g2[color[b]].push_back(color[a]);
}
continue;
}
if (color[b] == 0) {
dfsColor(b);
}
}
}
void dfs(int a) {
vis[a] = 1;
rmq[0][++top] = {dep[a], a};
ff[a] = ss[a] = top;
for (auto &b : g[a]) {
if (vis[b] == 0) {
par[b] = a;
dep[b] = 1 + dep[a];
dfs(b);
rmq[0][++top] = {dep[a], a};
ss[a] = top;
}
}
}
int getLca(int a, int b) {
if (ff[a] > ss[b]) {
swap(a, b);
}
assert(ff[a] <= ss[b]);
int k = lg2[b - a + 1];
return min(rmq[k][a], rmq[k][b - (1 << k) + 1]).second;
}
int dir[N];
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
///freopen ("input.txt", "r", stdin);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
dep[i] = -1;
}
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
xx[i] = a;
yy[i] = b;
sumEdge[i] = a + b;
g[a].push_back(i);
g[b].push_back(i);
}
/// build the Tree
dep[1] = 0;
dfs_build_bridges(1);
for (int i = 1; i <= n; i++) {
if (color[i] == 0) {
currentColor++;
dfsColor(i);
}
}
for (int i = 1; i <= n; i++) {
g[i] = g2[i];
}
for (int i = 1; i <= currentColor; i++) {
vis[i] = 0;
}
for (int i = 1; i <= currentColor; i++) {
if (vis[i] == 0) {
dep[i] = 0;
dfs(i);
}
}
for (int i = 2; i <= top; i++) {
lg2[i] = 1 + lg2[i / 2];
}
for (int k = 1; (1 << k) <= top; k++) {
for (int i = 1; i + (1 << k) - 1 <= top; i++) {
rmq[k][i] = min(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
}
}
exit(0);
/* exit(0);
for (int i = 1; i <= n; i++) {
cout << i << " : " << color[i] << "\n";
}
cout << "----------------\n";
for (int i = 1; i <= currentColor; i++) {
for (auto &j : g[i]) {
cout << "Edge = " << i << " " << j << "\n";
}
}
return 0;
for (int i = 1; i <= m; i++) {
if (isBridge[i]) {
cout << "bridge : " << xx[i] << " " << yy[i] << "\n";
}
}*/
cin >> q;
for (int i = 1; i <= q; i++) {
int a, b;
cin >> a >> b;
a = color[a];
b = color[b];
int c = getLca(a, b);
//cout << a << " " << b << " -> " << c << "\n";
while (a != c) {
assert(dir[a] == -1 || dir[a] == 0);
dir[a] = -1;
a = par[a];
}
while (b != c) {
assert(dir[b] == +1 || dir[b] == 0);
dir[b] = +1;
b = par[b];
}
}
for (int i = 1; i <= currentColor; i++) {
if (dir[i] != 0) {
pair<int, int> T = {i, par[i]};
assert(coresp.count(T));
sol[coresp[T]] = dir[i];
}
}
for (int i = 1; i <= m; i++) {
if (sol[i] == 0) {
cout << "B";
} else {
if (sol[i] == -1) {
cout << "R";
} else {
assert(sol[i] == +1);
cout << "L";
}
}
}
cout << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
