| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 45270 | bugmenot111 | One-Way Streets (CEOI17_oneway) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
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 <cstdlib>
#include <functional>
#include <queue>
#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;
struct bridge_tree {
static const int N = 100100;
static const int M = 100100;
std::vector<int> g[N];int U[M],V[M]; //edge list representation of the graph.
bool isbridge[M]; // if i'th edge is a bridge edge or not
int visited[N];int arr[N],T; //supporting arrays
int cmpno = 1;
std::queue<int> Q[N];
int adj(int u,int e){
return U[e]==u?V[e]:U[e];
}
int dfs0(int u,int edge) //marks all the bridges
{
visited[u]=1;
arr[u]=T++;
int dbe = arr[u];
for(int i=0;i<(int)g[u].size();i++)
{
int e = g[u][i];
int w = adj(u,e);
if(!visited[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;
return dbe;
}
void dfs1(int v) //Builds the tree with each edge a bridge from original graph
{
int currcmp = cmpno; // current component no.
Q[currcmp].push(v); // A different queue for each component, coz during bfs we shall go to another component (step of dfs) and then come back to this one and continue our bfs
visited[v]=currcmp;
while(!Q[currcmp].empty()) //bfs. Exploring all nodes of this component
{
int u = Q[currcmp].front();
Q[currcmp].pop();
for(int i=0;i<(int)g[u].size();i++)
{
int e = g[u][i];
int w = adj(u,e);
if(visited[w])continue;
//if the edge under consideration is bridge and
//other side is not yet explored, go there (step of dfs)
if(isbridge[e])
{
cmpno++;
dfs1(w);
}
else //else continue with our bfs
{
Q[currcmp].push(w);
visited[w]=currcmp;
}
}
}
}
};
std::vector<int> label_vertices(const int n, const int m, const edge_list& el) {
static struct bridge_tree bt;
std::vector<int> ans(n);
for(int i = 0; i < m; i++) bt.U[i] = el[i].first, bt.V[i] = el[i].second;
for(int i = 0; i < m; i++) bt.g[bt.U[i]].push_back(i);
for(int i = 0; i < m; i++) bt.g[bt.V[i]].push_back(i);
bt.dfs0(0, -1);
memset(bt.visited, 0, sizeof(bt.visited));
bt.dfs1(0);
for(int i = 0; i < n; i++) ans[i] = bt.visited[i] - 1;
return ans;
}
std::vector<int> f2lk_dfs_order; // so much for lambdas
void dfs(const labeled_edge_graph& tree, int v = 0, int p = -1) {
for(const auto& c: tree[v])
if(c.first != p) dfs(tree, c.first, v);
f2lk_dfs_order.push_back(v);
}
std::vector<int> get_dfs_order(const labeled_edge_graph& tree) {
dfs(tree);
return f2lk_dfs_order;
}
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 c: lab) printf("%d ", c);
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;
}