#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <limits.h>
using namespace std;
class Tree {
public:
vector<vector<int>> adj;
vector<vector<int>> dp;
vector<int> pre, post, depth, sub;
vector<int> parent;
int cntr = 0;
void dfs (int curNode, int prevNode) {
pre[curNode] = cntr++;
sub[curNode] = 1;
if (curNode == 0) depth[curNode] = 0;
else depth[curNode] = depth[prevNode] + 1;
for (int i: adj[curNode]) {
if (i != prevNode) {
dfs(i, curNode);
sub[curNode] += sub[i];
}
}
post[curNode] = cntr++;
}
bool isAncestor (int u, int v) {
return (pre[u] <= pre[v] && post[u] >= post[v]);
}
int lca (int u, int v) {
if (isAncestor(u, v)) return u;
else if (isAncestor(v, u)) return v;
for (int i = 31; i >= 0; i--) {
if (!isAncestor(dp[u][i], v)) {
u = dp[u][i];
}
}
return dp[u][0];
}
vector<pair<int,int>> directions;
vector<pair<int,int>> vec;
void add_query (int u, int v) {
if (u != lca(u, v)) directions.emplace_back(u, lca(u, v));
if (v != lca(u, v)) directions.emplace_back(lca(u, v), v);
vec.emplace_back(sub[u], u);
}
Tree (int n, vector<int> parent) {
this->parent.resize(n), adj.resize(n), sub.resize(n);
for (int i = 0; i < parent.size(); i++) {
if (parent[i] >= 0) {
adj[i].push_back(parent[i]), adj[parent[i]].push_back(i);
}
}
dp.resize(n), pre.resize(n), post.resize(n), depth.resize(n);
for (int i = 0; i < n; i++) {
dp[i].resize(32);
dp[i][0] = max(parent[i], 0);
}
for (int j = 1; j < 32; j++) {
for (int i = 0; i < n; i++) {
dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
}
dfs(0, -1);
}
int read () {
sort(vec.begin(), vec.end());
int root = vec[0].second;
queue<pair<int,int>> q;
//cout << root << '\n';
q.push({root, 0});
depth.assign(adj.size(), -1);
while (!q.empty()) {
pair<int,int> p = q.front(); q.pop();
if (depth[p.first] != -1) {
continue;
}
depth[p.first] = p.second;
for (int i: adj[p.first]) {
q.push({i, p.second + 1});
}
}
return vec[0].second;
}
};
class Graph {
public:
vector<vector<int>> adj;
vector<bool> hasVisited;
vector<int> parent;
void add_edge (int u, int v) {
adj[u].push_back(v), adj[v].push_back(u);
}
void dfs (int curNode) {
hasVisited[curNode] = true;
for (int i: adj[curNode]) {
if (!hasVisited[i]) {
parent[i] = curNode;
dfs(i);
}
}
}
Graph (int n) {
adj.resize(n);
}
Tree read() {
hasVisited.assign(adj.size(), false);
parent.assign(adj.size(), -1);
dfs(0);
Tree myTree(adj.size(), parent);
return myTree;
}
};
class BridgeFinder {
public:
int n; // number of nodes
vector<vector<int>> adj; // adjacency list of graph
vector<bool> visited;
vector<int> tin, low;
int timer;
map<pair<int,int>,bool> myMap;
void dfs(int v, int p = -1) {
visited[v] = true;
tin[v] = low[v] = timer++;
for (int to : adj[v]) {
if (to == p) continue;
if (visited[to]) {
low[v] = min(low[v], tin[to]);
} else {
dfs(to, v);
low[v] = min(low[v], low[to]);
if (low[to] > tin[v]) {
myMap[{v, to}] = myMap[{to, v}] = true;
}
}
}
}
void find_bridges() {
timer = 0;
visited.assign(n, false);
tin.assign(n, -1);
low.assign(n, -1);
for (int i = 0; i < n; ++i) {
if (!visited[i])
dfs(i);
}
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
vector<pair<int,int>> edges;
Graph g(N);
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
u--, v--;
edges.emplace_back(u, v);
g.add_edge(u, v);
}
Tree myTree = g.read();
int Q;
cin >> Q;
while (Q--) {
int u, v; cin >> u >> v; u--, v--;
myTree.add_query(u, v);
}
myTree.read();
BridgeFinder bf;
bf.n = g.adj.size();
bf.adj = g.adj;
bf.find_bridges();
for (int i = 0; i < M; i++) {
if (!bf.myMap[{edges[i].first, edges[i].second}]) {
cout << "B";
} else {
if (myTree.depth[edges[i].first] > myTree.depth[edges[i].second]) {
cout << "L";
} else {
cout << "R";
}
}
}
}
Compilation message
oneway.cpp: In constructor 'Tree::Tree(int, std::vector<int>)':
oneway.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int i = 0; i < parent.size(); i++) {
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
