Submission #45267

#	Time	Username	Problem	Language	Result	Execution time	Memory
45267		bugmenot111	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	3065 ms	262144 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 <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 (stderr)

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);
   ~~~~~^~~~~~~~~~~~~~~~

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