/*
if an edge is not a bridge it can be oriented either way;
the orientation of the bridges is uniquely determined;
let's call the input pairs "required pairs";
for each bridge B:
if there is no required pair with a node from the first component of the graph and the second component of the graph:
B can be oriented either way
otherwise: orient B the same way as the required pair from component A to component B
obviously, there cannot be two required pairs with different orientations because there can be no solution!
Algorithm:
Build "bridge tree" T of G
For every pair going from comp(u) to comp(v) in T:
orient all edges from comp(u) to LCA(comp(u), comp(v)) upwards
orient all edges from LCA(comp(u), comp(v)) to comp(v) downwards
The loop can be optimized by using a version of the difference array on the tree.
*/
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <numeric>
#include <string>
#include <functional>
#define MAXN 100100
typedef std::vector< std::pair<int, int> > edge_list;
typedef std::vector< std::vector<int> > graph;
typedef std::vector< std::vector< std::pair<int, int> > > labeled_edge_graph;
std::vector<int> label_vertices(const int n, const int m, const edge_list& el) {
static int dsu[MAXN];
static bool isbridge[MAXN];
static bool vis[MAXN];
static int T;
static int arr[MAXN];
std::vector<int> ans(n);
graph g(MAXN);
auto build_edge_graph = [&]{
size_t n = el.size();
for(size_t i = 0; i < n; i++) {
g[el[i].first].push_back(el[i].second);
g[el[i].second].push_back(el[i].first);
}
};
auto adj = [&](int u, int e) {
return el[e].first ^ el[e].second ^ u;
};
std::function<int(int)> f;
f = [&](int x)->int {
return dsu[x] == x ? x : dsu[x] = f(dsu[x]);
};
auto merge = [&](int x, int y) {
dsu[f(x)] = f(y);
};
std::function<int(int, int)> dfs0;
dfs0 = [&](int u, int edge)->int {
vis[u] = true;
int dbe = arr[u] = T++;
for(const auto& e: g[u]) {
int w = adj(u, e);
if(!vis[w]) dbe = std::min(dbe, dfs0(w, e));
else if(e != edge) dbe = std::min(dbe, arr[w]);
}
if(dbe == arr[u] && edge != -1) isbridge[edge] = true;
else if(edge != -1) merge(el[edge].first, el[edge].second);
return dbe;
};
build_edge_graph();
std::iota(dsu, dsu + MAXN, 0);
for(int i = 0; i < n; i++)
if(!vis[i]) dfs0(i, -1);
for(int i = 0; i < n; i++)
ans[i] = f(i);
int x = *std::min_element(ans.begin(), ans.end());
for(int i = 0; i < n; i++) ans[i] -= x;
return ans;
}
std::vector<int> get_dfs_order(const labeled_edge_graph& tree) {
std::vector<int> ans;
std::function<void(int, int)> dfs;
dfs = [&](int v, int p) {
for(const auto& c: tree[v]) if(c.first != p) dfs(c.first, v);
ans.push_back(v);
};
dfs(0, -1);
return ans;
}
struct f2lk_dsu {
int par[MAXN];
int rnk[MAXN];
int find(int x) {
return par[x] == x ? x : par[x] = find(par[x]);
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if(x == y) return;
if(rnk[x] > rnk[y]) par[y] = x;
else if(rnk[x] < rnk[y]) par[x] = y;
else if(rnk[x] == rnk[y]) rnk[par[y] = x]++;
}
f2lk_dsu() {
std::iota(par, par + MAXN, 0);
}
};
std::vector<int> offline_lca(const labeled_edge_graph& tree, const std::vector<int>& dfs_order, const edge_list& queries) {
static f2lk_dsu d;
static int ancestor[MAXN];
static bool black[MAXN];
static bool visited[MAXN];
static edge_list qr[MAXN];
std::vector<int> lc(queries.size());
for(int i = 0; i < queries.size(); i++) {
auto p = queries[i];
qr[p.first].push_back({p.second, i});
qr[p.second].push_back({p.first, i});
}
for(const int u: dfs_order) {
visited[u] = true;
for(const auto& p: tree[u]) if(visited[p.first]) {
int v = p.first;
d.unite(u, v);
ancestor[d.find(u)] = u;
}
black[u] = true;
for(const auto& p: qr[u])
if(black[p.first]) lc[p.second] = ancestor[d.find(p.first)];
}
return lc;
}
std::string solve(const int n, const int m, const int p, const edge_list& el, const edge_list& pairs) {
static int up_edges[MAXN];
static int down_edges[MAXN];
static bool visited[MAXN];
static std::string ans(m, 'B');
labeled_edge_graph tree(MAXN);
edge_list p2(pairs);
auto lab = label_vertices(n, m, el); // build bridge-block tree
for(int i = 0; i < m; i++) {
int x = lab[el[i].first];
int y = lab[el[i].second];
if(x != y) {
tree[x].push_back({y, i});
tree[y].push_back({x, i});
}
}
for(auto& p: p2)
p = {lab[p.first], lab[p.second]};
std::sort(p2.begin(), p2.end());
p2.erase(std::unique(p2.begin(), p2.end()), p2.end());
auto dfs_order = get_dfs_order(tree);
auto lc = offline_lca(tree, dfs_order, p2);
for(int i = 0; i < p2.size(); i++) {
int x = p2[i].first;
int y = p2[i].second;
int l = lc[i];
up_edges[x]++;
up_edges[l]--;
down_edges[y]++;
down_edges[l]--;
}
for(int i: dfs_order) {
visited[i] = true;
int pedge = -1;
for(const auto& p: tree[i]) {
if(!visited[p.first]) pedge = p.second;
else {
up_edges[i] += up_edges[p.first];
down_edges[i] += down_edges[p.first];
}
}
if(pedge == -1) continue;
if(up_edges[i] == 0 && down_edges[i] != 0) ans[pedge] = el[pedge].first == i ? 'R' : 'L';
else if(up_edges[i] != 0 && down_edges[i] == 0) ans[pedge] = el[pedge].first == i ? 'L' : 'R';
}
return ans;
}
int main(void) {
int n, m, p;
scanf("%d%d", &n, &m);
edge_list edges(m);
for(int i = 0; i < m; i++) {
int x;
int y;
scanf("%d%d", &x, &y);
edges[i] = {x - 1, y - 1};
}
scanf("%d", &p);
edge_list pairs(p);
for(int i = 0; i < p; i++) {
int x;
int y;
scanf("%d%d", &x, &y);
pairs[i] = {x - 1, y - 1};
}
puts(solve(n, m, p, edges, pairs).c_str());
return 0;
}
Compilation message
oneway.cpp: In function 'std::vector<int> label_vertices(int, int, const edge_list&)':
oneway.cpp:30:14: warning: variable 'isbridge' set but not used [-Wunused-but-set-variable]
static bool isbridge[MAXN];
^~~~~~~~
oneway.cpp: In function 'std::vector<int> offline_lca(const labeled_edge_graph&, const std::vector<int>&, const edge_list&)':
oneway.cpp:111:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < queries.size(); i++) {
~~^~~~~~~~~~~~~~~~
oneway.cpp: In function 'std::__cxx11::string solve(int, int, int, const edge_list&, const edge_list&)':
oneway.cpp:151:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < p2.size(); i++) {
~~^~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:178:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:183:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:186:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &p);
~~~~~^~~~~~~~~~
oneway.cpp:191:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3065 ms |
262144 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3065 ms |
262144 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3065 ms |
262144 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
