Submission #45273

#	Time	Username	Problem	Language	Result	Execution time	Memory
45273		bugmenot111	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	137 ms	146168 KiB

oneway

/*
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 <cstring>
#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);
	std::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;
		ancestor[u] = u;
		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(n);
	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;
}

Compilation message (stderr)

oneway.cpp: In function 'std::vector<int> offline_lca(const labeled_edge_graph&, const std::vector<int>&, const edge_list&)':
oneway.cpp:139: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:181: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:208: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:213: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:216:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &p);
  ~~~~~^~~~~~~~~~
oneway.cpp:221:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40