#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cassert>
#include <map>
#define ll long long
using namespace std;
const int NMAX = 1e5;
const int LOGMAX = 18;
struct Edge {
int to, type, id;
};
int n, m, q, t, components;
pair<int, int> edges[NMAX + 1];
vector<Edge> g[NMAX + 1], tree[NMAX + 1];
vector<pair<int, int>> updates[NMAX + 1];
int dfs_time[NMAX + 1];
int low[NMAX + 1];
bool bridge[NMAX + 1];
int component[NMAX + 1];
Edge parent[NMAX + 1];
int depth[NMAX + 1];
int euler[2 * NMAX + 1], ind_e;
int LOG[2 * NMAX + 1];
int pos_euler[NMAX + 1];
int rmq[LOGMAX + 1][2 * NMAX + 1];
int answer[NMAX + 1];
pair<int, int> node_with_depth[NMAX + 1];
void DFS1(int node, int dad = 0) {
dfs_time[node] = low[node] = ++t;
for(auto [next_node, type, id] : g[node]) {
if(!dfs_time[next_node]) {
DFS1(next_node, node);
low[node] = min(low[node], low[next_node]);
if(low[next_node] > dfs_time[node]) {
bridge[id] = 1;
}
}
else if(next_node != dad) {
low[node] = min(low[node], dfs_time[next_node]);
}
}
}
void DFS2(int node) {
component[node] = components;
for(auto [next_node, type, id] : g[node]) {
if(!component[next_node] && !bridge[id]) {
DFS2(next_node);
}
}
}
void DFS3(int node, Edge dad_edge = {0, 0, 0}) {
parent[node] = dad_edge;
depth[node] = depth[dad_edge.to] + 1;
euler[++ind_e] = node;
pos_euler[node] = ind_e;
for(auto [next_node, type, id] : tree[node]) {
if(next_node != dad_edge.to) {
DFS3(next_node, {node, type, id});
euler[++ind_e] = node;
}
}
}
void Precompute() {
for(int i = 2; i <= ind_e; i++) {
LOG[i] = LOG[i >> 1] + 1;
}
for(int i = 1; i <= ind_e; i++) {
rmq[0][i] = euler[i];
}
for(int k = 1; (1 << k) <= ind_e; k++) {
for(int i = 1; i + (1 << k) - 1 <= ind_e; i++) {
int first_node = rmq[k - 1][i];
int second_node = rmq[k - 1][i + (1 << (k - 1))];
rmq[k][i] = (depth[first_node] < depth[second_node] ? first_node : second_node);
}
}
}
int GetLCA(int x, int y) {
x = pos_euler[x];
y = pos_euler[y];
if(x > y) {
swap(x, y);
}
int k = LOG[y - x + 1];
int first_node = rmq[k][x];
int second_node = rmq[k][y - (1 << k) + 1];
return (depth[first_node] < depth[second_node] ? first_node : second_node);
}
void UpdatePath(int x, int y, int type_need) {
while(x != y && !answer[parent[x].id]) {
assert(x > 0);
Edge curent_edge = parent[x];
answer[curent_edge.id] = 1 + (type_need ^ curent_edge.type);
x = curent_edge.to;
}
}
void Update(int lca, int x, int y) {
UpdatePath(x, lca, 1);
UpdatePath(y, lca, 0);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
edges[i] = {a, b};
g[a].push_back({b, 0, i});
g[b].push_back({a, 1, i});
}
for(int i = 1; i <= n; i++) {
if(!dfs_time[i]) {
DFS1(i);
}
}
for(int i = 1; i <= n; i++) {
if(!component[i]) {
components++;
DFS2(i);
}
}
for(int i = 1; i <= n; i++) {
for(auto [j, type, id] : g[i]) {
if(component[i] != component[j]) {
tree[component[i]].push_back({component[j], type, id});
}
}
}
for(int i = 1; i <= n; i++) {
if(!depth[i]) {
DFS3(i);
}
}
Precompute();
cin >> q;
while(q--) {
int x, y;
cin >> x >> y;
x = component[x];
y = component[y];
updates[GetLCA(x, y)].push_back({x, y});
}
for(int i = 1; i <= n; i++) {
node_with_depth[i] = {depth[i], i};
}
sort(node_with_depth + 1, node_with_depth + n + 1);
for(int i = 1; i <= n; i++) {
int node = node_with_depth[i].second;
for(auto [x, y] : updates[node]) {
Update(node, x, y);
}
}
for(int i = 1; i <= m; i++) {
if(answer[i] == 0) {
cout << "B";
}
else if(answer[i] == 1) {
cout << "R";
}
else {
cout << "L";
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |