#include <vector>
#include <iostream>
#include <algorithm>
#define int int64_t
using namespace std;
struct edge
{
int from, to, nr;
bool bridge = false;
char ch = 'U';
int getend(int fr)
{
if (fr == from) return to;
return from;
}
bool l = false;
bool r = false;
};
int log2(int n)
{
return 32 - __builtin_clz(n) - 1;
}
struct graph
{
vector<edge> edges;
vector<vector<int>> edgepointers;
vector<int> paredges;
vector<vector<int>> parents;
vector<int> levels;
vector<int> visited;
int ln1;
int n;
int dfs(int curr, int from, int &num)
{
visited[curr] = num;
num++;
int gmin = visited[curr];
for (int nep : edgepointers[curr])
{
edge e = edges[nep];
int next = e.getend(curr);
if (nep == from) continue;
if (visited[next] == -1)
{
int nv = dfs(next, nep, num);
if (nv > visited[curr]) edges[nep].bridge = true;
gmin = min(gmin, nv);
}
gmin = min(gmin, visited[next]);
}
return gmin;
}
vector<bool> visisec;
void structurize(int curr, int par, int pare)
{
if (visisec[curr]) return;
visisec[curr] = true;
if (par != -1) levels[curr] = levels[par] + 1;
else levels[curr] = 0;
paredges[curr] = pare;
parents[0][curr] = par;
for (int nep : edgepointers[curr])
{
int next = edges[nep].getend(curr);
structurize(next, curr, nep);
}
}
void buildlct(int in)
{
n = in;
ln1 = log2(n) + 1;
for (int i = 1; i < ln1; i++)
{
for (int j = 0; j < n; j++)
{
if (parents[i - 1][j] == -1) parents[i][j] = -1;
else parents[i][j] = parents[i - 1][parents[i - 1][j]];
}
}
}
int lca(int a, int b)
{
if (levels[b] > levels[a]) swap(a, b);
int ldiff = levels[a] - levels[b];
for (int i = 0; i < ln1; i++)
{
if (ldiff & (1LL<<i))
{
a = parents[i][a];
}
}
if (a == b) return a;
for (int i = ln1 - 1; i > -1; i--)
{
if (parents[i][a] != parents[i][b])
{
a = parents[i][a];
b = parents[i][b];
}
}
if (a == b) return a;
return parents[0][a];
}
vector<int> upwards;
vector<int> downwards;
void finalize()
{
vector<pair<int,int>> order;
for (int i = 0; i < n; i++)
{
order.push_back({-levels[i], i});
}
sort(order.begin(), order.end());
for (auto p : order)
{
int curr = p.second;
if (curr == 0) continue;
int par = parents[0][curr];
if (downwards[curr] != -1 && levels[downwards[curr]] < levels[curr])
{
if (edges[paredges[curr]].bridge)
{
edges[paredges[curr]].r = (curr == edges[paredges[curr]].to);
edges[paredges[curr]].l = (curr == edges[paredges[curr]].from);
}
if (downwards[par] == -1)
{
downwards[par] = downwards[curr];
}
else if (levels[downwards[curr]] < levels[downwards[par]]) downwards[par] = downwards[curr];
}
if (upwards[curr] != -1 && levels[upwards[curr]] < levels[curr])
{
if (edges[paredges[curr]].bridge)
{
edges[paredges[curr]].l = (curr == edges[paredges[curr]].to);
edges[paredges[curr]].r = (curr == edges[paredges[curr]].from);
}
if (upwards[par] == -1)
{
upwards[par] = upwards[curr];
}
else if (levels[upwards[curr]] < levels[upwards[par]]) upwards[par] = upwards[curr];
}
}
}
};
signed main()
{
int n, m;
cin >> n >> m;
graph g;
g.edgepointers.resize(n);
for (int i = 0; i < m; i++)
{
edge e;
cin >> e.from >> e.to;
e.from--;
e.to--;
e.nr = i;
g.edges.push_back(e);
g.edgepointers[e.from].push_back(g.edges.size() - 1);
g.edgepointers[e.to].push_back(g.edges.size() - 1);
}
int num = 0;
g.visited.resize(n, -1);
g.dfs(0, -1, num);
for (int i = 0; i < m; i++)
{
if (!g.edges[i].bridge) g.edges[i].ch = 'B';
}
g.visisec.resize(n, false);
g.levels.resize(n, -1);
g.parents.resize(log2(n) + 1, vector<int>(n, -1));
g.paredges.resize(n, -1);
g.structurize(0, -1, -1);
g.buildlct(n);
g.upwards.resize(n, -1);
g.downwards.resize(n, -1);
int q;
cin >> q;
for (int i = 0; i < q; i++)
{
int a, b;
cin >> a >> b;
a--; b--;
int lc = g.lca(a, b);
if (g.upwards[a] != -1)
{
if (g.levels[g.upwards[a]] > g.levels[lc]) g.upwards[a] = lc;
}
else g.upwards[a] = lc;
if (g.downwards[b] != -1)
{
if (g.levels[g.downwards[b]] > g.levels[lc]) g.downwards[b] = lc;
}
else g.downwards[b] = lc;
}
g.finalize();
for (int i = 0; i < m; i++)
{
if (g.edges[i].ch == 'U')
{
if (g.edges[i].r) g.edges[i].ch = 'R';
else if (g.edges[i].l) g.edges[i].ch = 'L';
else g.edges[i].ch = 'B';
}
}
for (int i = 0; i < m; i++)
{
cout << g.edges[i].ch;
}
cout << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
