#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 DisjointSetUnion {
public:
vector<int> compSize, parent;
int find_head (int u) {
while (u != parent[u]) u = parent[u];
return u;
}
void join (int u, int v) {
u = find_head(u), v = find_head(v);
if (compSize[u] > compSize[v]) swap(u, v);
parent[u] = v, compSize[v] += compSize[u];
}
DisjointSetUnion (int n) {
parent.resize(n), compSize.assign(n, 1);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
};
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;
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;
vector<vector<int>> adj;
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);
}
}
}
};
string process (vector<pair<pair<int,int>,int>> edges, vector<pair<int,int>> queries) {
set<int> s;
for (auto& p: edges) {
s.insert(p.first.first), s.insert(p.first.second);
}
map<int,int> myMap; int cntr = 0;
for (int i: s) {
myMap[i] = cntr++;
}
for (int i = 0; i < edges.size(); i++) {
edges[i].first.first = myMap[edges[i].first.first];
edges[i].first.second = myMap[edges[i].first.second];
}
for (int i = 0; i < queries.size(); i++) {
queries[i].first = myMap[queries[i].first];
queries[i].second = myMap[queries[i].second];
}
Graph g(s.size());
for (auto& p: edges) {
g.add_edge(p.first.first, p.first.second);
}
BridgeFinder bf;
bf.n = s.size();
bf.adj.resize(s.size());
for (auto& p: edges) {
bf.adj[p.first.second].push_back(p.first.first);
bf.adj[p.first.first].push_back(p.first.second);
}
bf.find_bridges();
DisjointSetUnion dsu(s.size());
for (auto& p: edges) {
if (!bf.myMap[{p.first.first, p.first.second}]) {
dsu.join(p.first.first, p.first.second);
}
}
Tree myTree = g.read();
for (auto& q: queries) {
//cout << q.first << " " << q.second << " " << s.size() << '\n';
if (dsu.find_head(q.first) != dsu.find_head(q.second)) {
//cout << q.first << " " << q.second << '\n';
myTree.add_query(q.first, q.second);
}
}
//return "3";
myTree.read();
string str = "";
for (int i = 0; i < edges.size(); i++) {
if (!bf.myMap[{edges[i].first.first, edges[i].first.second}]) {
str += 'B';
} else {
if (myTree.depth[edges[i].first.first] > myTree.depth[edges[i].first.second]) {
str += 'L';
} else {
str += 'R';
}
}
}
return str;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
vector<pair<pair<int,int>,int>> edges;
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
u--, v--;
edges.push_back({{u, v}, i});
}
vector<pair<int,int>> queries;
int Q;
cin >> Q;
while (Q--) {
int u, v; cin >> u >> v; u--, v--;
queries.emplace_back(u, v);
}
DisjointSetUnion dsu(N);
for (auto& p: edges) {
dsu.join(p.first.first, p.first.second);
}
vector<vector<pair<pair<int,int>,int>>> edges1(N);
vector<vector<pair<int,int>>> queries1(N);
for (auto& p: edges) {
edges1[dsu.find_head(p.first.first)].push_back(p);
}
for (auto& p: queries) {
queries1[dsu.find_head(p.first)].push_back(p);
}
string ansr;
ansr.resize(M);
for (int i = 0; i < N; i++) {
if (i != dsu.find_head(i)) continue;
string s = process(edges1[i], queries1[i]);
for (int j = 0; j < edges1[i].size(); j++) {
ansr[edges1[i][j].second] = s[j];
}
}
cout << ansr;
}
Compilation message
oneway.cpp: In constructor 'Tree::Tree(int, std::vector<int>)':
oneway.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for (int i = 0; i < parent.size(); i++) {
| ~~^~~~~~~~~~~~~~~
oneway.cpp: In function 'std::string process(std::vector<std::pair<std::pair<int, int>, int> >, std::vector<std::pair<int, int> >)':
oneway.cpp:188:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
188 | for (int i = 0; i < edges.size(); i++) {
| ~~^~~~~~~~~~~~~~
oneway.cpp:192:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
192 | for (int i = 0; i < queries.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
oneway.cpp:225:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
225 | for (int i = 0; i < edges.size(); i++) {
| ~~^~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:274:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
274 | for (int j = 0; j < edges1[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
